数据结构之堆详解
1.概述
堆（也叫优先队列），是一棵完全二叉树，它的特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆）。它常用于管理算法执行过程中的信息，应用场景包括堆排序，优先队列等。
2.堆的基本操作
堆是一棵完全二叉树，高度为O（lgn），其基本操作至多与树的高度成正比。在介绍堆的基本操作之前，先介绍几个基本术语：
A：用于表示堆的数组，下标从1开始，一直到n
PARENT(t)：节点t的父节点，即floor(t/2)
RIGHT(t)：节点t的左孩子节点，即:2*t
LEFT(t)：节点t的右孩子节点，即:2*t+1
HEAP_SIZE(A)：堆A当前的元素数目
下面给出其主要的四个操作（以大顶堆为例）：
2.1Heapify(A,n,t)
该操作主要用于维持堆的基本性质。假定以RIGHT(t)和LEFT(t)为根的子树都已经是堆，然后调整以t为根的子树，使之成为堆。
voidHeapify(intA[],intn,intt)
{
intleft=LEFT(t);
intright=RIGHT(t);
intmax=t;
if(left<=n) max=A[left]>A[max]?left:max;
if(right<=n) max=A[right]>A[max]?right:max;
if(max!=A[t])
{
swap(A,max,t);
Heapify(A,n,max);
}
}
2.2 BuildHeap(A,n)
该操作主要是将数组A转化成一个大顶堆。思想是，先找到堆的最后一个非叶子节点（即为第n/2个节点），然后从该节点开始，从后往前逐个调整每个子树，使之称为堆，最终整个数组便是一个堆。
voidBuildHeap(intA[],intn)
{
inti;
for(i=n/2;i<=n;i++)
Heapify(A,n,i);
}
2.3GetMaximum(A,n)
该操作主要是获取堆中最大的元素，同时保持堆的基本性质。堆的最大元素即为第一个元素，将其保存下来，同时将最后一个元素放到A[1]位置，之后从上往下调整A，使之成为一个堆。
voidGetMaximum(intA[],intn)
{
intmax=A[1];
A[1]=A[n];
n--;
Heapify(A,n,1);
returnmax;
}
2.4 Insert(A,n,t)
向堆中添加一个元素t，同时保持堆的性质。算法思想是，将t放到A的最后，然后从该元素开始，自下向上调整，直至A成为一个大顶堆。
voidInsert(intA[],intn,intt)
{
n++;
A[n]=t;
intp=n;
while(p>1&&A[PARENT(p)]<t)
{
A[p]=A[PARENT(p)];
p=PARENT(p);
}
A[p]=t;
returnmax;
}
3. 堆的应用
3.1 堆排序
堆的最常见应用是堆排序，时间复杂度为O(NlgN)。如果是从小到大排序，用大顶堆；从大到小排序，用小顶堆。
3.2 在O(nlgk)时间内，将k个排序表合并成一个排序表，n为所有有序表中元素个数。
【解析】取前100万个整数，构造成了一棵数组方式存储的具有小顶堆，然后接着依次取下一个整数，如果它大于最小元素亦即堆顶元素，则将其赋予堆顶元素，然后用Heapify调整整个堆，如此下去，则最后留在堆中的100万个整数即为所求100万个数字。该方法可大大节约内存。
3.3一个文件中包含了1亿个随机整数，如何快速的找到最大(小)的100万个数字?（时间复杂度：O（nlgk））
4.总结
堆是一种非常基础但很实用的数据结构，很多复杂算法或者数据结构的基础就是堆，因而，了解和掌握堆这种数据结构显得尤为重要。
5.参考资料
（1）经典算法教程《算法导论》