基本数据结构 —— 堆以及堆排序（C++实现）

目录

• 什么是堆
• 堆的存储
• 堆的操作
• 堆排序
• 测试代码
• 例题
• 参考资料

什么是堆

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

通常将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的存储

堆一般使用数组存储。当堆中有n个元素的时，可以将这些元素存放在数组array的前n个单元里，其中堆的根节点中元素存放在array[1]中。结点之间的关系有两种情况：

• 如果根节点在数组中的位置是1，那么第i个位置的左右节点下标分别为2i、2i+1，父节点下标为i/2。
• 如果根节点在数组中的位置是0，那么第i个位置的左右节点下标分别为2i+1、2i+2，父节点下标为⌊（i-1） /2⌋。
  

堆的操作

以大根堆为例，给出堆支持的一些操作。

结构体定义

struct Heap
{
    int size;   // number of elements in array
    int *array;
    Heap()  //init
    {
        size = 0;
        array = new int[maxn];
    }
    Heap(int n) //init
    {
        size = 0;
        array = new int[n];
    }
    ~Heap() //free memory
    {
        delete array;
    }
};

判断是否为空

    bool empty()
    {
        if(size != 0) return false;
        return true;
    } 

往堆中插入元素

    void insert(int value)
    {
        array[++size] = value; // 数组的最末尾插入新节点
        int index = size;
        while(index > 1)    // 自下而上地调整子节点与父节点的位置
        {
            // 如果大于父节点的值，根据最大堆的特点，子节点上升，而父节点要下降
            if(array[index] > array[index/2]) swap(array[index],array[index/2]);
            index /= 2; // 继续向上搜索
        }
    }

从堆中删除元素

    void del()
    {
        if(empty()) return; // 删除前不能为空
        swap(array[1],array[size--]); //用数组最末尾节点覆盖被删节点
        int index = 1;
        while(2*index <= size) // 从上到下调整二叉堆
        {
            int next = 2*index;
            // 选取子节点中最大的
            if(next < size && array[next+1] > array[next]) next++;
            // 与子节点中最大的比较，如果小于则当前结点下降
            if(array[index] < array[next])
            {
                swap(array[index],array[next]);
                index = next;
            }
            else break;
        }
    }

取出堆中最大的元素

    int max() {
        if(empty()) return -1;
        return array[1];
    }

堆排序

给定一个有size个元素的数组array,可用下面的算法buildHeap(array,size)在 O(n) 时间内将数组array调整为一个堆。

void buildHeap(int array[],int size)
{
    int i,tmp,index;
    for(i = size/2; i >= 1; i--)
    {
        tmp = array[i];
        index = 2*i;
        while(index <= size)
        {
            if(index < size && array[index+1] > array[index]) index++;
            if(array[index] < tmp) break;
            array[index/2]  = array[index];
            index *= 2;
        }
        array[index/2] = tmp;
    }
}

测试代码

#include<iostream>
#include<algorithm>
#define maxn 1001   //heap's size

using namespace std;

struct Heap {
    int size;   // number of elements in array
    int *array;
    Heap() {    //init
        size = 0;
        array = new int[maxn];
    }
    Heap(int n) {   //init
        size = 0;
        array = new int[n];
    }
    ~Heap() {   //free memory
        delete array;
    }
    bool empty() {
        if(size != 0) return false;
        return true;
    }
    void insert(int value) {
        array[++size] = value;
        int index = size;
        while(index > 1) {
            if(array[index] > array[index/2]) swap(array[index],array[index/2]);
            index /= 2;
        }
    }
    void del()
    {
        if(empty()) return;
        swap(array[1],array[size--]);
        int index = 1;
        while(2*index <= size)
        {
            int next = 2*index;
            if(next < size && array[next+1] > array[next]) next++;
            if(array[index] < array[next])
            {
                swap(array[index],array[next]);
                index = next;
            } else break;
        }
    }
    int max() {
        if(empty()) return -1;
        return array[1];
    }
};
void buildHeap(int array[],int size) {
    int i,tmp,index;
    for(i = size/2; i >= 1; i--) {
        tmp = array[i];
        index = 2*i;
        while(index <= size) {
            if(index < size && array[index+1] > array[index]) index++;
            if(array[index] < tmp) break;
            array[index/2]  = array[index];
            index *= 2;
        }
        array[index/2] = tmp;
    }
}
int main() {
    int n,i,j,k;
    cout << "input heap's size:";
    cin >> n;
    Heap H = Heap(n);
    int* array = new int[n];
    for(i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        array[i] = tmp;
        H.insert(tmp);
    }
    buildHeap(array,n);
    for(i = 1; i <= n; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
    while(!H.empty()) {
        cout << H.max() << endl;
        H.del();
    }
    return 0;
};

结果：

例题

最小的K个数 —— 剑指offer

class Solution {
public:
    struct Heap {
        int size;   // number of elements in array
        int *array;
        Heap() {    //init
            size = 0;
            array = new int[1001];
        }
        Heap(int n) {   //init
            size = 0;
            array = new int[n];
        }
        ~Heap() {   //free memory
            delete array;
        }
        bool empty() {
            if(size != 0) return false;
            return true;
        }
        void insert(int value) {
            array[++size] = value;
            int index = size;
            while(index > 1) {
                if(array[index] < array[index/2]) swap(array[index],array[index/2]);
                index /= 2;
            }
        }
        void del()
        {
            if(empty()) return;
            swap(array[1],array[size--]);
            int index = 1;
            while(2*index <= size)
            {
                int next = 2*index;
                if(next < size && array[next+1] < array[next]) next++;
                if(array[index] > array[next])
                {
                    swap(array[index],array[next]);
                    index = next;
                } else break;
            }
        }
        int min() {
            if(empty()) return -1;
            return array[1];
        }
    };
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        int i,n = input.size();
        if(n < k) return ret;
        Heap H = Heap(n);
        for(i = 0;i < n;i++)
        {
            H.insert(input[i]);
        }
        while(k)
        {
            ret.push_back(H.min());
            H.del();
            k--;
        }
        return ret;
    }
};

参考资料

• 数据结构图文解析之：二叉堆详解及C++模板实现
• 《数据结构（C语言描述）（修订版）》电子工业出版社