6. 堆排序

堆排序也是一种时间复杂度为$\Omicron (n\lg n)$的排序算法，但是与归并排序不同的是堆排序是一种原址排序，也就是说排序过程只是交换数据的位置。

最大堆

堆是一个数组，存储一个近似完全二叉树，树上的每个结点对应数组中的一个元素，数组第一个元素存储根节点，第i个元素的左孩子在数组的2i位置，右孩子在数组的2i+1位置，父结点在数组的i/2位置。

最大堆指一种父节点必然大于等于子节点的堆。下图为一个最大堆的存储情况：

MAX-HEAPIFY（维护最大堆）

MAX-HEAPIFY是维护最大堆性质的重要方法。MAX-HEAPIFY的输入为数组A和下标i，当调用MAX-HEAPIFY时，假定根节点为LEFT(i)和RIGHT(i)的二叉树都是最大堆，但是A[i]可能比它的子节点要小。MAX-HEAPIFY通过让A[i]的值在最大堆中逐级下降，从而使得以下标i为根节点的树符合最大堆的性质。以下是MAX-HEAPIFY的伪代码以及MAX-HEAPIFY(A, 2)的处理过程：

因为堆的高度为$\lg n$，所以该过程的时间复杂度是$\Omicron (\lg n)$.

建堆

自下而上的调用MAX-HEAPIFY可以把一个数组转换为最大堆。
叶子节点不需要调用，所以从下标为n/2的的元素开始，一直到根节点。
伪代码和建堆过程如下：

堆排序

1. 利用BUILD-MAX-HEAP方法构建最大堆
2. 接着循环的堆的根节点和最后一个元素交换
3. 堆的大小减一
4. 调用MAX-HEAPIFY(A, 1)
5. 循环2-4步，直到堆中只剩根节点

伪代码，以及2-5步过程如下：

优先队列

堆除了堆排序还有很多应用，比如优先队列。优先队列也有两种最大优先队列和最小优先队列。
一个最大优先队列支持以下操作：

1
2
3
4

INSERT(S, x)
MAXIMUM(S)
EXTRACT-MAX(S)
INCREASE-KEY(S, x, k)

最大优先队列的应用有很多，其中一个是在共享计算机系统的作业调度。最大优先队列记录将要执行的各个作业及他们之间的相对优先级。
最小优先队列可以被用于基于事件驱动的模拟器。队列中保存要模拟的事件，每个事件都有一个发生时间作为其关键字。

涉及算法

点击查看实现

• 堆排序

习题答案

思考题

• 6-43 Young氏矩阵