堆，是优先队列最常用的一种实现方式。在优先队列中，每个元素都被赋予了一个优先级，而每次出队时都让优先级最高的元素出队。堆，则是一种存储优先队列的方法，特指以一棵树形式存储的优先队列。最常用的是二叉堆，但既然是专门介绍数据结构，就不妨说全一些，我们取4个典型的堆进行比较，见下表（此表及表下备注，来自于广东省中山市第一中学黄源河前辈的《左偏树的特点及其应用》，并做过言辞修改及内容补充）：

       在此说明几点：

0、二项堆又称Bernoulli堆，左偏树又称左堆；斜堆并未在表中列出，是由于其复杂度与左偏树相同，没必要单独列出。其代码更简单，但常数较大，且在特殊数据下可能退化成O(n)。它与左偏树的关系，就像Splay与AVL的关系，并无优劣之分，前者更简洁灵活而后者更快。另外，我并未谈及D堆，那是因为这类仅在接触外存才值得应用的堆，我并不想提及。大家在考试用不上，平时也用不上，故而在我看来暂时了解、理解就好，之后真正用到了再去深究不迟。

1、二项堆，其“取最小点”的复杂度是O(log n)，可以改进为O(1)。方法是，随时记录最小节点，并只在插入、删除以及合并等操作进行的时候更新该记录。

2、二项堆，其“插入”操作的平均时间复杂度为O(1)，表中给出的是最坏时间复杂度。

3、Fibonacci堆，其“删除最小点”和“删除任意点”两个操作的时间复杂度均为平摊时间复杂度。

       可能大家并未了解全，那就请自行搜索吧，我在此仅仅给出实现代码。由于种类过多，我仅仅对每种堆给出一种最常见的实现方式（例如二叉堆仅仅给出数组实现法），大家视题目需要而融会贯通即可。另外，由于代码较长，为了方便大家比较，我仅仅给出类版，实际实现时，不写成类有时反而方便许多。

       还有，我依旧假设每个元素的信息仅有一个int权值，这样可以让大家更关注代码的框架结构，而不至于在繁琐的代码中看得迷迷糊糊。真正使用时，如果元素信息增多，视情况修改即可。

代码：

// 本代码所实现的是最小堆const int maxk = 10;const int maxn = 1024;inline swap(int &x,int &y) { int t=x; x=y; y=t; }// 二叉堆// 实现了init、in、out操作class Two_Heap{    int H[maxn+1],L; // H[1~L]是堆中元素    void up(int i)    {        int j=i>>1;        if(i==1) return;        if(H[i]>=H[j]) return;        swap(H[i],H[j]); up(j);    }    void down(int i)    {        int j=i<<1;        if(j>L) return;        if(j!=L && H[j+1]<H[j]) ++j;        if(H[i]<=H[j]) return;        swap(H[i],H[j]); down(j);    }public:    Two_Heap():L(0) {}    void init(int A[],int N)    {        // 以一个数组A[1~N]去初始化堆，这是堆排中建堆的过程，复杂度O(N)        L=N;        for(int i=1;i<=N;++i) H[i]=A[i];        for(int i=N>>1;i>=1;--i) down(i); // 可以证明，从N/2开始调整即可，后N/2个点必然是叶子结点    }    void in(int x) { A[++L]=x; up(L); }    int out() { swap(A[1],A[L--]); down(1); return A[L+1]; }    int min() { return A[1]; }};// 未完待续

《数据结构》C++代码 堆（优先队列）