堆是一棵完全二叉树，对于最大堆来说，任何一个非叶子节点满足：结点的值大于其孩子结点的值。使用数组可以实现完全二叉树的结构。下标从1开始，一个结点i的左孩子下标为2*i，有孩子下标为2*i+1。下面是实现一个简单的最大堆。

 

const int maxn = 100000;class MaxHeap{public:    MaxHeap(int maxElementsCnt = maxn){        elems = (int*)malloc((maxElementsCnt + 1) * sizeof(int));        size = 0;    }    int maxElement(){        return elems[1];    }    int top(){        int maxElem = elems[1];        int lastElem = elems[size--];        int i, child;        for (i = 1; i * 2 <= size; i = child){            child = i * 2;            if (child != size && elems[child + 1] > elems[child])                child++;            if (lastElem < elems[child])                elems[i] = elems[child];            else                break;        }        elems[i] = lastElem;        return maxElem;    }    void push(int val){        int i;        for (i = ++size; i > 1 && elems[i / 2] < val; i /= 2){            elems[i] = elems[i / 2];        }        elems[i] = val;    }    ~MaxHeap(){        delete[] elems;     }private:    int* elems;    int size;};