算法导论第6.4章 - 堆排序算法

伪代码利用了维护堆和建立堆的部分

堆排序

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)

建立堆

BUILD-MAX-HEAP(A)
  A.heap-size = A.length
  for i = int(A.length / 2) downto 1
    MAX-HEAPIFY(A, 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)

在建立好的堆里面，根部的元素是最大的，然后把这个最大的元素和A[n]进行替换，
剩下的节点再进一步进行维护堆的性质和建立堆，如此递归到调整完所有元素，
结束的时候可以获得排好序的数组。

HEAPSORT的复杂程度为 O(nlgn)