堆（heap），是一种特殊的数据结构。之所以特殊，因为堆的形象化是一个棵完全二叉树，并且满足任意节点始终不大于（或者不小于）左右子节点（有别于二叉搜索树Binary Search Tree）。其中，前者称为小顶堆（最小堆，堆顶为最小值），后者为大顶堆（最大堆，堆顶为最大值）。然而更加特殊的是，通常使用数组去存储堆，而不是二叉树。关于完全二叉树，可以参见另一篇博文http://www.cnblogs.com/eudiwffe/p/6207196.html
// Heap is a sepcial complete binary tree(CBT)
/* Heap sketch is a CBT, but stored in Array
* 9 ---> maxtop 7 7
* / \ / \ / \
* / \ / \ / \
* 7 8 4 8 4 5
* / \ / \ / \ / /
* / \ / \ / \ / /
* 5 3 2 4 3 5 3 6
*
* (1) (2) (3)
* maxtop heap not maxtop(mintop) not heap(CBT)
* */
具体而言，对于长度为N的数组A中的任意一个元素i（0<=i<N/2），其左右子节点为i*2+1和i*2+2。以大顶堆为例，该堆始终满足:
A[i]>=A[i*2+1] && A[i]>=A[i*2+2]。（下文不做特殊说明均以大顶堆为例）
如何创建一个堆呢？对于给定的一个数组arr[]和长度n，一般使用在数组上就地堆化。堆化的过程实际是调整堆的过程。有自上到下和自下到上两种堆化方法。
1）自上到下构建堆
// Method 1
// Create (Initialize) Heap, from top to bottom
void heap_create(int arr[], int n)
{
int i; // from top to bottom
for(i=1; i<n; heap_adjust(arr,i++));
}
自上到下很好理解，首先假设当前数组arr的前i个元素已经满足堆性质（arr[0]只有一个元素肯定满足）；然后每次在数组之后添加一个元素A[i]，使得新的数组A[0~i]满足堆化性质，其中heap_adjust可以调整当前节点i使其满足堆化；直到i为n时，调整完毕，即堆化完毕。其中heap_adjust如下：
void heap_adjust(int arr[], int c)
{ // c - children, p - parent
int p = (c-1)>>1, temp;
// heap adjust from maxtop, from bottom to top
for(; arr[p]<arr[c]; c=p, p=(c-1)>>1){
temp = arr[p];
arr[p] = arr[c];
arr[c] = temp;
}
} // Time O(logn)
调整代码也很好理解，首先找到当前节点c的父节点p，如果arr[p]<arr[c]，则交换，然后继续寻找p的父节点进行调整；否则，调整完毕（因为前文已经假设，数组的前i-1已经满足堆化，新添一个元素i进行调整）。
很有意思，构建堆时使用自上到下，那么调整堆就必须自下到上。
2）自下到上构建堆
// Method 2
// Create (Initialize) Heap, from bottom to top
void heap_create(int arr[], int n)
{
int i; // from bottom to top
for(i=(n>>1)-1; i>-1; heap_adjust(arr,i--,n));
}
此处自下到上的“下”，并不是数组最后一个元素，而是最后一个父节点n/2-1。也就是以父节点为线索，逐渐调整该节点的子节点。因此，此处heap_adjust是自上到下的调整，如下
void heap_adjust(int arr[], int p, int n)
{ // c - children, p - parent
int maxid=p, temp;
// heap_adjust for maxtop, from top to bottom
for(; p<(n>>1); p=maxid){
if ((p<<1)+1<n && arr[(p<<1)+1]>arr[maxid])
maxid = (p<<1)+1;
if ((p<<1)+2<n && arr[(p<<1)+2]>arr[maxid])
maxid = (p<<1)+2;
if (maxid == p) break;
// swap arr[maxid] and arr[p]
temp = arr[maxid];
arr[maxid] = arr[p];
arr[p] = temp;
}
} // Time O(logn)
首先保证当前p节点是作为父节点，然后在找到其子节点p*2+1和p*2+2，在三者中选择最大的一个maxid，然后交换；否则调整结束。
两种构建堆的方法各有利弊，方法1）是逐渐增加新节点，堆的节点增加方法数组尾部；方法2）是逐渐删除堆顶节点，然后在剩下的节点中寻找最大的放在堆顶（一般会将数组尾元素与堆顶交换，以保证其符合完全二叉树结构）。堆的调整时间复杂度均为O(logn)，堆的创建时间复杂度均为O(nlogn)。
3）堆排序
堆的常见应用是堆排序。堆排序方法十分巧妙，无须额外空间，直接在原数组中进行堆排序。对于给定的数组arr[]以及其长度n，首先进行原地堆化，上面两种方法均可，推荐第二种；然后每次将堆顶元素与数组尾元素交换，即arr[0]与arr[n-1]交换；将数组arr[]以及其长度n-1进行堆调整，此调整使用2）中的调整方法；反复迭代，直到调整数组的长度为1为止，排序完毕。
以非降序排序为例，每次删除堆顶的元素放入数组尾部，所以需要使用大顶堆。
// Heap Sort - ascending order
void heap_sort(int arr[], int n)
{
int i, temp;
// init maxtop heap, using method 2 (from bottom to top)
for (i=(n>>1)-1; i>-1; heap_adjust(arr,i--,n));
for (i=n-1; i>0; heap_adjust(arr,0,i--)){
// mv heap top to end (heap top is max)
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
}
} // Time O(nlogn)
每次调整堆，只需将堆顶调整即可。堆化时间复杂度为O(nlogn)，排序时间复杂度为O(nlogn)，总的时间复杂度为O(nlogn)。因为调整堆必须使用自上到下的方法调整heap_adjust，所以使用方法2）进行堆化和调整，十分巧妙。
4）TopK问题
TopK问题描述：在N个无序元素中，找到最大的K个（或最小的K）。
如果使用排序类似的算法，其时间复杂度为O(NlogN)+O(K)。当N远大于K时，例如N为1e9，而K为10时，这种方法显然太慢。使用堆化和堆调整则可以快速解决。以下以寻找最小的K个元素为例。
设有一个K长度的最大堆，如果在数组中有一个元素小于该堆顶，则该元素有可能为寻找的最小K元素之一。则将该元素替换堆顶，然后进行堆调整。反复迭代，直到遍历了数组中的所有元素。此时，该长度为K的最大堆就是待寻找的TopK。
// TopK problem : find max k (or min k) elements from unordered set
// eg. find min k elements from arr[], stored in res[]
void topk(int arr[], int n, int res[], int k)
{
int i; // copy and k elements to res
for (i=0; i<k; res[i]=arr[i],++i);
// make maxtop heap for res[]
for(i=(k>>1)-1; i>-1; heap_adjust(res,i--,k));
for(i=k; i<n; ++i){
if (res[0] <= arr[i]) continue;
// now arr[i] < heap top
res[0] = arr[i];
heap_adjust(res,0,k);
}
} // Time O(nlogk)
其中arr[]为原始无序数据，res[]为寻找结果。堆调整使用2）中的调整方法。首先任意选择无序数组arr[]中的K个元素，对其进行堆化；然后从K开始遍历无序数组arr[]，每次将比堆顶小的放入堆顶，然后堆调整；最后得到堆res[]为TopK结果。其时间复杂度：创建K个元素堆O(KlogK)，寻找最小K元素O((N-K)logK)，总时间复杂度为O(NlogK)，（当N远大于K时）。
对于寻找最大K个元素，则需要构建最小堆，以及最小堆的堆调整，不再赘述。
注：本文涉及的源码：https://git.oschina.net/eudiwffe/codingstudy/blob/master/src/heap/heap.c