算法描述

堆排序(heapsort)与归并排序一样，但不同于插入排序的是，其时间复杂度为。而与插入排序相同，但不同于归并排序的是，堆排序同样具有空间原址性：任何时候只需要常数个额外的元素空间存储临时数据。
在堆排序算法中，我们使用的是最大堆。最小堆通常用于构造优先队列。
(二叉)堆是一个数组，它可以被看成一个近似的完全二叉树。除了最底层外，该树是完全充满的，而且是从左到右填充。表示堆的数组A包含两个属性：A.length(通常)给出数组元素的个数，A.heap-size表示有多少个堆元素存储在该数组中。也就是说，虽然A[1..A.length]可能都存有数据，但只有A[1..A.heap-size]中存放的是堆的有效元素，这里，0≤A.heap-size≤A.length。

维护堆的性质

MAX-HEAFIFY用于维护最大堆的性质。它的输入为一个数组和一个下标i。在调用MAX-HEAPIFY的时候，我们假定根节点为LEFT(i)和RIGHT(i)的二叉树都是最大堆，但这是A[i]有可能小于其孩子，这违背了最大堆的性质。MAX-HEAPIFY通过让A[i]的值在最大堆中“逐级下降”，从而使得以下标i为根节点的子树重新遵循最大堆的性质。

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
if largest != i
  exchange A[i] with A[largest]
  MAX-HEAPIFY(A, largest)

MAX-HEAPIFY示例

时间复杂度为O(lgn)，即O(h)。

建堆

可以用自底向上的方法利用过程MAX-HEAPIFY把一个大小为n=A.length的数组A[1..n]转换为最大堆。子数组中的元素都是树的叶子节点。每个叶节点都可以看成只包含一个元素的堆。过程BUILD-MAX-HEAP对树中的其它节点都调用一次MAX-HEAPIFY。

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

时间复杂度： O(n)。

构建堆的示例

堆排序算法

初始时，堆排序算法利用BUILD-MAX-HEAP将输入数组A[1..n]建成最大堆，其中n=A.length。因为数组中的最大元素总在根节点A[1]中，通过把它与A[n]进行互换，我们可以让该元素放到正确的位置。这时，如果我们从堆中去掉节点n（通过减少A.heap-size的值实现），剩余的节点中，原来根的孩子节点仍然是最大堆，而新的根节点可能会违背最大堆的性质。为了维护最大堆的性质，我们要做的是调用MAX-HEAPIFY(A, 1)，从而在A[1..n-1]上构造一个新的最大堆。最排序算法会不断重复这一过程，直到堆的大小从n-1降到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)

HEAPSORT运行过程（部分）

优先级队列

优先级队列是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字。一个最大优先级队列支持以下操作:

• INSERT(S, x): 把元素x插入集合S中。
• MAXIMUM(S): 返回S中具有最大键字的元素。
• EXTRACT-MAX(S): 去掉并返回S中具有最大键字的元素。
• INCREASE-KEY(S, x, k): 将元素x的关键字值增加到k，这里假设k的值不小于x的原关键字值。

HEAP-MAXIMUM(A)
return A[1]

时间复杂度Θ(1)。

HEAP-EXTRACT-MAX(A)
if A.heap-size < 1
  error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
return max

时间复杂度为O(lgn)。

HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
  error "new key is smaller than current key"
A[i] = key
while i > 1 and A[PARENT(i)] < A[i]
  exchange A[i] with A[PARENT(i)]
  i = PARENT(i)

时间复杂度为O(lgn).

MAX-HEAP-INSERT(A, key)
A.heap-size = A.heap-size + 1
A[A.heap-size] = -INF
HEAP-INCREASE-KEY(A, A.heap-size, key)

运行时间O(lgn)。

特性：

堆排序为非稳定排序