Preview
接下来的几章我们会把所有的排序都讲完。
keywords: 维护堆 建堆 优先队列
先修知识： 排序有很多应用。比如银行对数据库中的编号进行排序，专业软件内的图层按次序来排序。
如果输入的数组仅有常数个元素需要在排序过程中储存在原数组之外，那么相关的排序算法就被称为是原址的。堆排、快排都是原址排序算法。决策树模型可以用来研究基于比较的排序算法的性能局限。
书上的排序运行时间比较图
一个二叉树，在最后一层的所有结点都集中在最左边，而在其他所有层的结点数都达到应有的理论上限，这样的二叉树是完全二叉树。堆是数组，但可以被看成是一个近似的完全二叉树。
一个堆的下标i应该按照每层向右、逐层往下、下层必定大于上层的顺序标注。以下代码可以计算一个结点的父结点和子结点：
PARENT (i)
return⌊i/2⌋
LEFT(i)
return 2i
RIGHT(i)
return 2i+1
维护堆的性质
最大堆的性质是指除了根以外的所有结点i都要满足： A[PARENT(i)] >= A[i]
最小堆的性质是指除了根以外的所有结点i都要满足： A[PARENT(i)] <= A[i]
下面以最大堆为例子：
MAX-HEAPIFY(A,i)
l = LEFT(i) //参照preview里的内容
r = RIGHT(i)
if l <= A.size and A[l] > A[i] //先考虑左子节点
largest = l
else largest = i
if r <= A.size and A[r] > A[largest] //再考虑右子节点
largest = r
if largest != i //如果根节点不是大的值，做下列两操作
exchange A[i] with A[largest]
MAX-HEAPIFY(A,largest)//继续操作
上面的伪代码大致是维护最大堆的核心代码。找出根、左、右结点中最大的，并执行交换或不交换，若交换则进行递归调用MAX-HEAPIFY。交换结点实质交换的是这个结点及其所有子结点。当然，有意思的是正是因为堆的结点排列方式，我们可以提前知道一个结点的所有子节点的下标。找最大值的过程时，左子结点优先于右子结点，以保证堆的下标次序仍然是按顺序的。
调整一次结点的关系耗费Θ(1)。在堆最底层恰好半满的时候，T(n)的递归式刚好变成最坏情况，为T(2n/3) + Θ(1)（证明过程略）。因此，按照我们在第四章学过的主定理的第二种情况，这个递归式的解为T(n) = O(logn)（因为这是上界的情况，所以O就把Θ替换了）
按照上述解来推导，我们也就得到了，树高为h（其中h = logn）的堆想要维护最大堆或最小堆的性质，耗费时间的上界为h。
建堆
仍然以最大堆为例，我们只要让一个数组A满足最大堆的性质即算建堆。之前我们提出的MAX-HEAPIFY算法，已经可以不断地通过交换数组中的元素（这个元素指结点及其子节点的集合）来保证数组维持最大堆的性质。因此建最大堆的伪代码比较简单：
BUILD-MAX-HEAP(A)
A.size = A.length
for i = ⌊A.length/2⌋ downto 1
MAX-HEAPIFY(A,i)
由于堆的下标顺序的本身性质，从⌊A.length/2⌋+1到A.length的下标所指的结点全都是叶子，不用考虑与子节点的交换。⌊A.length/2⌋到1的下标所指的结点全部要遍历地维护性质。
为了验证建堆算法的正确性，我们可以把结点i+1,i+2,…,n都是某一个最大堆的根节点当作循环不变式。这句话的隐含意思是随着每次循环i值的减少，判断是 最大堆的根节点 的结点范围也应当同时增大。我们只需要用数学归纳法，按照 初始化 ， 保持 ， 终止 三步走就很容易得证，（所以过程就略了）。
注意，MAX-HEAPIFY本身是一个递归算法，因此BUILD-MAX-HEAP算法的时间复杂度并不那么容易算出来。
过程我就偷下懒不写了……一堆求和公式。最后得出来时间复杂度上界是O(n)。也就是说可以在线性时间内把一个无序数组构造成为一个最大堆或最小堆。
堆排序
算法
利用维护堆的性质的算法，我们可以把一个无序数组变成一个堆。这个堆所代表的数组显然不是递增或递减的，但我们知道它的元素是按堆的规则排序的。接下来我们只要按一定的算法，每次都把最大的点提取出来，再把剩下的树继续维护成最大堆，循环操作直到所有的点都提取出来：
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.size = A.size – 1
MAX-HEAPIFY(A,1)
构建堆耗时的复杂度为O(n)，维护堆的性质耗时的复杂度为O(logn)，一共维护n-1次，因此堆排序的时间复杂度是O(nlogn)。
堆排的核心思想是首先构建一个堆，每次抓取根节点的值，然后剩下的结点继续维护成堆。堆排的胜利是数学的胜利。正是因为堆这个数据结构只要求一层比一层大，一团数据比另一团数据大，因此时间复杂度才能降到nlogn。堆排序也就成了一个优秀的算法。它结合了插入排序和归并排序的两种优点——消耗时间小的同时具有空间原址性。
实现优先队列
优先队列是堆排序的一个重要应用。操作系统的作业调度又是优先队列的一个重要应用。最大堆实现最大优先队列，最小堆实现最小优先队列。我们依然以最大堆为例，它实现的最大优先队列支持下列操作：
MAXIMUM(S)：返回S中具有最大键字的元素
EXTRACT-MAX(S)：去掉并返回S中的具有最大键字的元素
INCREASE-KEY(S,x,k)：将元素x的关键字值增加到k，这里假设k值不小于x的原关键字值
INSERT(S,x)：把元素x插入集合S中
按上述顺序思考下伪代码。MAXIMUM很容易，只要return A[1]就行了。EXTRACT-MAX和堆排中的循环部分差不多。INCREASE把指定位置的结点升值，然后需要往上交换以维护最大堆的性质。INSERT是在叶子加一个无限小的值，再利用INCREASE升值并维护。