用数组实现一个简单的heap（最大堆）结构

make_heap函数用来从给定的任意顺序的数组创建一个最大堆。

push_heap函数向堆中压入一个新的数据，并维持堆的形态。

pop_heap函数取出堆中最大的元素，并将该元素从堆结构中剔除，维持堆的形态。

使用了定长数组作为基本的存储数据的结构，当数组空间满时，重新申请一个两倍长于当前数组的新数组，将元素复制过去。

heap.cpp

#include <iostream>#include "heap.cpp"using namespace std;int main(){heap p;int A[10] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};p.make_heap(A, 10);p.push_heap(13);for(int i = 0; i < 10; i++)cout<<p.pop_heap()<<" ";}

最小堆的使用实例：

Find_Top_K问题：数组N中寻找最大的K个元素：

用前K[0...k-1]个元素，建立小顶堆K-Min-Heap；

遍历K...N-1元素，和堆顶元素比较：

小于跳过，

大于则替换堆顶元素，调整K-Min-Heap结构使之保持小顶堆特性；

K-Heap的操作时间为log2(k)

插入法建堆和上面代码中使用的调整法建堆效率是有差距的，插入法建堆指的是从一个元素的堆开始，依次向堆中插入数据，并调整堆，最后得到最大堆。调整法建堆的时间复杂度为：O(n)，而插入法建堆的最坏时间复杂度为：O(nlgn)