1. 简述
堆（也叫优先队列），是一棵完全二叉树，它的特性是父节点的值超过（低于）两个子连接点的值（各自称之为大顶堆和小顶堆）。它常见于管理方法优化算法实行全过程中的信息内容，应用领域包含堆排序，优先队列等。
2. 堆的操作过程
堆是一棵完全二叉树，高宽比为O（lg n），其操作过程最多与树的高宽比正相关。在详细介绍堆的操作过程以前，先详细介绍好多个基础专业术语：
- 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.1 Heapify(A,n,t)
该实际操作关键用以保持堆的基础特性。假设以RIGHT(t)和LEFT(t)为根的子树都早已是堆，随后调节以t为根的子树，使之变成堆。
void Heapify(int A[], int n, int t) {
int left = LEFT(t);
int right = RIGHT(t);
int max = 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/两个连接点），随后从该连接点逐渐，从后面向前逐一调节每一个子树，使之称之为堆，最后全部二维数组就是一个堆。
void BuildHeap(int A[], int n) {
int i;
for(i = n/2; i<=n; i )
Heapify(A, n, i);
}
2.3 GetMaximum(A,n)
该实际操作主要是获得堆中较大 的原素，另外维持堆的基础特性。堆的较大 原素即是第一个原素，将其储存出来，另外将最后一个原素放进A[1]部位，以后从上向下调节A，使之变成一个堆。
void GetMaximum(int A[], int n) {
int max = A[1];
A[1] = A[n];
n--;
Heapify(A, n, 1);
return max;
}
2.4 Insert(A, n, t)
向堆中加上一个原素t，另外维持堆的特性。优化算法观念是，将t放进A的最终，随后从该原素逐渐，自下往上调节，直到A变成一个大顶堆。
void Insert(int A[], int n, int t) {
n ;
A[n] = t;
int p = n;
while(p >1 && A[PARENT(p)] < t) {
A[p] = A[PARENT(p)];
p = PARENT(p);
}
A[p] = t;
return max;
}
3. 堆的运用
3.1 堆排序
堆的最普遍运用是堆排序，算法复杂度为O(N lg N)。如果是由小到大排列，用大顶堆；从大到小排列，用小顶堆。
3.2 在O(n lg k)時间内，将k个排列表合拼成一个排列表，n为全部有序表中原素数量。
【分析】取前100 万只整数金额，结构变成一棵二维数组方法储存的具备小顶堆，随后然后先后取下一个整数金额，假如它超过最少原素亦即堆顶原素，则将其授予堆顶原素，随后用Heapify调节全部堆，这般下来，则最终留到堆中的一百万个整数金额即是所愿 一百万个数据。该方式可大大的节省运行内存。
3.3 一个文档中包括了一亿个任意整数金额，怎么才能的寻找较大 (小)的一百万个数据?（算法复杂度：O（n lg k））
4. 小结
堆是一种十分基本但很好用的算法设计，许多 繁杂优化算法或是算法设计的基本便是堆，因此，掌握和把握堆这类算法设计看起来至关重要。
5. 参考文献
（1）经典算法实例教程《算法导论》
