MAX-HEAPIFY(A,i): 依次调整使A[i]为根的子树成为最大堆，是堆排序的重要子程序；
BUILD-MAX-HEAP(A):
1. heap-size[A] ← length[A]
2. for i ← ⌊length[A]/2⌋ downto 1 //从最后一个节点的父节点开始调整
3. do MAX-HEAPIFY(A,i)
HEAPSORT(A):
1. BUILD-MAX-HEAP(A)
2. for i ← length[A] downto 2
3. do exchange A[1] ↔ A[i]
4. heap-size[A] ← heap-size[A] -1
5. MAX-HEAPIFY(A,1)
HEAPSORT的时间复杂度为Ο(nlgn);而且最坏和最佳运行时间都是Ω(nlgn)
最大优先级队列支持的操作:
INSERT(S,x)
MAXIMUM(S): 返回S中具有最大关键字的元素
EXTRACT-MAX(S): 去掉并返回S中的具有最大关键字的元素
INCREASE-KEY(S,x,k): 将元素x的关键字的值增加到k
HEAP-EXTRACT-MAX(A): 跟堆排序一样
MAX-HEAP-INSERT(A,key):
1. heap-size[A] ← heap-size[A] + 1
2. A[heap-size[A]] ← -∞
3. HEAP-INCREASE-KEY(A, heap-size[A] , key)
PARTITION(A,p,r):
1. x ← A[r]
2. i ← p-1
3. for j ← p to r - 1
4. do if A[j] £ x
5. then i ← i+1
6. exchange A[i] ↔ A[j]
7. exchange A[i+1] ↔ A[r]
8. return i+1
QUICKSORT(A,p,r)
1. if p < r
2. then q ← PARTITION(A,p,r)
3. QUICKSORT(A,p,q-1)
4. QUICKSORT(A,q+1,r)