排序和顺序统计量

排序算法 插入排序最坏情况下可以在 $\Theta(n^2)$ 时间内将 $n$ 个数排好序。但是由于其内层循环非常紧凑，对于小规模输入，插入排序是一种非常快的原址排序算法(输入数组中仅有常数个元素需要在排序过程中储存在数组之外)。归并排序有更好的渐进运行时间，但归并过程不是原址的。

顺序统计量 一个 $n$ 个数的集合的第 $i$ 个顺序统计量就是集合中第 $i$ 小的数。

堆排序

堆排序与归并排序一样，但不同于插入排序，堆排序的时间复杂度为 $O(n\mathrm{lg}n)$ ；与插入排序相同，但不同于归并排序的事，堆排序同样具有空间原址性：任何时候都只需要常数个额外的元素空间储存临时数据。

堆排序引入“堆”这个数据结构来管理信息，堆不仅用于堆排序，也可以构造一种有效的优先队列。

堆

二叉堆是一个数组，可以被看成近似的完全二叉树。除最底层外完全充满，而且是从左向右填充。表示堆的数组A有两个属性：A.length表示元素个数，A.heap-size表示有多少堆元素，表示的是堆有多少个有效元素，因此A.length>=A.heap-size.这里设根节点为A[1]

将数组在逻辑上排列成如图所示

则我们可以观察出对于给定的下标 $i$ ，我们如何访问父节点(除以2取整)和左右子节点(分别为 $2i$ 和 $2i+1$ )。大多数计算机可以通过左移或右移在一条指令时间内计算出父节点和左子节点。堆排序好的实现中，这三个访问函数通常作为宏或内联函数。

二叉堆分为最大堆和最小堆，上图就是一个最大堆，它需要满足任何一个节点的值一定小于等于其父节点，因此根节点一定是最大的。最小堆则相反，根节点一定是最小的，且对每一节点都满足节点值大于等于父节点值。

把堆看成一棵树，定义堆中节点的高度就是该节点到叶子节点最长简单路径上边的数目，进而用根节点的高度来定义堆的高度，因此堆的高度是 $\Theta(\mathrm{lg}n)$ 。

下面分成几部分拆解堆排序的过程

维护堆的性质

想象这样一种情况，根节点的左右子树都是最大堆，但根节点本身可能小于左子节点或右子节点，因此对整个堆而言违背了最大堆的性质，我们采用让根节点逐级下降的方式调整堆，使它找到自己合适的位置。A为整个数组，i为需要调整的位置，LEFT，RIGHT，PARENT分别代表获取左子节点，右子节点和父节点的位置。

MAX-HEAPIFY(A, i)
l = LEFT(i)	//左子节点下标
r = RIGHT(i)	//右子节点下标
if l <= A.heap-size and A[l] > A[i]
	largest = l
else largest = i
if r <= A.heap-size and A[r] > A[largest]
	largest = r	//以上代码找到了i，i左子节点，i右子节点三者最大值的位置
if largest != i
	exchange A[i] with A[largest]	//至此保证了i下面一层符合最大堆
	MAX-HEAPIFY(A, largest)	//如果i的元素被换到了下一层去，仍然有可能比再下一层的子节点小，因此需要递归检查

过程如图所示

分析上式时间代价：调整根、左、右三个元素的关系的时间代价 $\Theta(1)$ ，加上在一棵以 $i$ 的一个孩子为根节点的子树上递归的时间代价，每个孩子的子树大小至多为 $2n/3$ ，在树的最底层恰好半满时，设左半部分满，则左子树占整个树的部分最大。设总共 $k$ 层，则根节点左子树有 $2^{k-1}-1$ 个节点，底层半满情况下，整个树共有 $2^{k-1}-1+\frac{1}{2}\cdot2^{k-1}=\frac{3}{2}\cdot2^{k-1}-1$ 个节点（除最后一层外都是规律的，最后一层要除以2），显然，比值具有上界 $2/3$ 。

因此有 $T(n)\le T(2n/3)+\Theta(1)$

根据主定理，解为 $T(n)=O(\mathrm{lg}n)$ 。因此若树高为 $h$ ，该算法时间复杂度就为 $O(h)$ ，因为高度和总节点数存在对数关系。

建堆

采用自底向上的方法将某乱序数组转化为最大堆。每个叶子节点看成是只包含一个元素的堆，因此只需从倒数第二层的最右侧开始，从右向左、从下向上建堆，这样可以确保实际最大的元素慢慢浮到最顶端的根节点。

BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = [A.length/2] downto 1
	MAX-HEAPIFY(A, i)

估算一下时间上界，for循环是 $O(n)$ ，每次维护堆是 $O(\mathrm{lg}n)$ ，因此共计 $O(n\mathrm{lg}n)$ 。实际上可以更精确的估计一下：包含 $n$ 个元素的堆的高度为 $[lgn]$ (设有k层，则总节点数的范围是 $2^{k-1}\le n\le 2^{k}-1$ ，因此 $\mathrm{lg}n<\mathrm{lg}(n+1)\le k\le \mathrm{lg}n+1$ )，对于任意一个包含 $n$ 个元素的堆中，至多有 $\lceil n/2^{k+1}\rceil$ 个高度为h的节点，因此总代价为

堆排序算法

首先把某数组建成最大堆，虽然并不是完全有序，但我们可以保证最大元素一定是根节点，我们将这个最大节点与最右侧的叶子节点(最后一个节点)互换，最大元素就到了正确的位置，这个时候我们再对除了末尾的那个最大元素以外剩下的元素重新维护最大堆，只不过这时候堆就比原来少了一个固定好位置的那个元素了，不断重复这个过程，从大到小的元素逐渐放到正确的位置，堆也逐渐变小，直到剩下2个，至此已经完全排好顺序。

HEAPSORT(A)
BUILD-MAX-HEAP(A)	//建堆
for i = A.length downto 2
	exchange A[1] with A[i]	//把根(最大值)替到堆的末尾
	A.heap-size = A.heap-size - 1	//缩减堆，处理剩下的数据
	MAX-HEAPIFY(A, 1)	//由于非常小的值被换到了根的位置，需要进行一次维护堆

灰色代表固定好位置后，不再参与后续的排序。

优先队列 优先队列的每个元素都有一个关键字用来排序，一个优先队列中应当有以下几个操作：插入，返回最大元素，去掉最大元素，增加某元素的关键字值

最大优先队列的应用：共享计算机系统的作业调度，一个作业完成后，选出最大元素代表的作业(最高优先级)执行，通过插入某元素到正确的位置可以把一个新作业加入到队列中。