用数组实现堆

这里实现一个最小堆

实现堆关键在于堆调整，堆有向上调整和向下调整，当pop堆顶元素的时候是弹出数组里面最小的元素，这个时候需要向下调整堆，把堆顶元素的值更新为数组末尾元素的值，然后从堆顶开始向下调整堆

    int pop() {if(empty())return -1;int temp=data[0];std::swap(data[0],data[--heapSize]);adjustDown(0);return temp;}

从树根节点开始，找出左右子树中比自己更小的节点，交换值，然后从交换后的节点处继续往下寻找更小的节点，直到堆末尾或者没有更小的

    void adjustDown(int root) {int left = 2 * root + 1;int right = left + 1;int next = root; // 找到比根节点小的if (left < heapSize && data[left] < data[next])next = left;if (right < heapSize && data[right] < data[next])next = right;if (next != root) {std::swap(data[next], data[root]);adjustDown(next);}}

push元素的时候先放到数组末尾，然后看看容量是不是满了，增长一下容量，开始从数组末尾向上调整堆 

    void push(int value) {data[heapSize] = value;++heapSize;if (heapSize == volume) {grow();}adjustUp();}

向上调整堆先找出当前节点的父节点，如果父节点是更大的节点，那么交换值后往上走，继续向上寻找更大的节点

    void adjustUp() {int index=heapSize-1;int parent=(index-1)/2;while(index>0&&data[parent]>data[index]) {std::swap(data[index],data[parent]);index=parent;parent=(index-1)/2;}}

完整代码

class Heap {int volume = 8;int heapSize = 0;int back = 0;int front = 0;int *data = nullptr;void grow() {int *temp = new int[2 * volume];for (int i = 0; i < volume; ++i) {temp[i] = data[i];}delete[]data;data = temp;volume *= 2;}void adjustUp() {int index=heapSize-1;int parent=(index-1)/2;while(index>0&&data[parent]>data[index]) {std::swap(data[index],data[parent]);index=parent;parent=(index-1)/2;}}void adjustDown(int root) {int left = 2 * root + 1;int right = left + 1;int next = root; // 找到比根节点小的if (left < heapSize && data[left] < data[next])next = left;if (right < heapSize && data[right] < data[next])next = right;if (next != root) {std::swap(data[next], data[root]);adjustDown(next);}}public:Heap() {data = new int[volume];}void push(int value) {data[heapSize] = value;++heapSize;if (heapSize == volume) {grow();}adjustUp();}int pop() {if(empty())return -1;int temp=data[0];std::swap(data[0],data[--heapSize]);adjustDown(0);return temp;}int top() {if(empty())return -1;return data[0];}bool empty() const {return heapSize == 0;}bool size() const {return heapSize;}
};