算法导论-排序和顺序统计量-堆排序(缺代码)

堆排序

(二叉)堆是一个数组，它可以被看成一个近似的完全二叉树。树上的每一个结点对应数组中的一个元素。除了最底层外，该树是完全充满的，而且是从左像右填充。

在堆排序中，我们使用的是最大堆。最小堆通常用于构造优先队列。

在最大堆中，最大堆性质是指除了根以外的所有结点i都要满足:A[Panrent(i)]≥a[i]，也就是说，某个结点的值至多与其父结点一样大。堆中的最大元素存放在根结点中。

把堆看成一棵树，一个堆中的结点的高度就为该结点到叶结点最长简单路径上边的数目。

优先队列是一种用来维护一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字(key)。一个最大优先队列支持以下操作:
Insert(S,x):把元素x插入集合S中。这一操作等价于S=S∪{x}。
Maximum(S):返回S中具有最大键字的元素。
Extract-Max(S):去掉并返回S中的具有最大键字的元素。
Increase-Key(S,x,k):将元素x的关键字值增加到k，k的值不小于x的原关键字。