数据结构:经典二叉堆

堆的性质：

1.根节点比左右叶子节点大(小)
2.完全二叉树，最后一层都在左侧

堆的存储

堆可以用数组存储

c++实现一个大顶堆

#include <algorithm>
#include <cassert>

using namespace std;


template<typename Item>
class MaxHeap{

private:
    Item *data;
    int count;
    int capacity;
    

    void shiftUp(int k){
        while( k > 1 && data[k/2] < data[k] ){
            swap( data[k/2], data[k] );
            k /= 2;
        }
    }

    void shiftDown(int k){
        while( 2*k <= count ){
            int j = 2*k;
            if( j+1 <= count && data[j+1] > data[j] ) j ++;
            if( data[k] >= data[j] ) break;
            swap( data[k] , data[j] );
            k = j;
        }
    }

public:

    MaxHeap(int capacity){
        data = new Item[capacity+1];
        count = 0;
        this->capacity = capacity;
    }

    MaxHeap(Item arr[], int n){
        data = new Item[n+1];
        capacity = n;

        for( int i = 0 ; i < n ; i ++ )
            data[i+1] = arr[i];
        count = n;

        for( int i = count/2 ; i >= 1 ; i -- )
            shiftDown(i);
    }

    ~MaxHeap(){
        delete[] data;
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }

    void insert(Item item){
        assert( count + 1 <= capacity );
        data[count+1] = item;
        shiftUp(count+1);
        count ++;
    }

    Item extractMax(){
        assert( count > 0 );
        Item ret = data[1];
        swap( data[1] , data[count] );
        count --;
        shiftDown(1);
        return ret;
    }

    Item getMax(){
        assert( count > 0 );
        return data[1];
    }
};

构建最大堆的方法:

1.将n个元素逐个插入到一个空堆中，算法复杂度是O(nlogn)
每次插入都要构建一次最大堆,
每次和父节点比较，若大于父节点，交换位置，还要防止下标越界
也就是 "shift up"
2.heapify的过程，算法复杂度为O(n)
从最后一个非叶子节点的父节点开始，
相当于减少了一半的元素
也就是 "shift down"

堆应用

1.优先级队列
普通队列一般都是先进先出，优先级队列后进，但有可能先出
比如说,医院里排队看病，如果遇到有急诊病人的话，可以在队列的前面优先看病。还有机场排队过安检，如果有乘客飞机即将起飞了，一般机场会有紧急安检通道，可以让比较着急的乘客优先过安检。
优先队列可以构造一个大顶堆，新插入的元素来维持这个大顶堆，每次从根节点取出元素。
2.从10亿个数中取出前100个最大的数
若是这10亿个数，用快速排序，nlogn的时间复杂的，
可是10亿个数，如果一个数占4byte的话，10亿个数大约快4G，
如果计算机内存2G的话，一次读取时放不下的。
可以在内存中维护100个数的小顶堆，若是新来的元素比对顶元素小，直接放弃继续从剩余元素中查找，如果比对堆顶大，则替换堆顶元素，可以用shift down方法在构建一个小顶堆。
此时算法的时间复杂度是nlog(m),也就是 10亿*log(100)
3.多路归并排序
一般归并排序，将数组分为两份，多路含义可以将数组分为多份，d份，
d越大，归并的层级也就越低，到时每次比较d个数，时间复杂的是O(d),
如果这个d个数构造一个小顶堆来比较，将堆顶元素取出后，在相应的路上，后移动取出下一个元素，再构造一个小顶堆，这个时间复杂度就是O(dlog(d))