最大堆 算法：

 

1、保持堆的性质。 MAX-HEAPIFY(A, i)从结点i开始保持二叉堆的性质，通过比较左子树，把最大的赋值给A【largest】，再比较右子树，最大的赋值给A【largest】，比较i 和 largest相不相等，不等则互换A[largest]和A[i]，并且递归调用MAX-HEAPIFY（A,largest)。

 

代码：

1 MAX-HEAPIFY(A, i) 2  3       l←LEFT(i) 4  5      r←RIGHT(i) 6  7      if l≤heap-size[A] and A[l]>A[i] 8  9           then largest←l10 11            else largest←i12 13      if r≤heap-size[A] and A[r]>A[largest]14 15           then largest←r16 17      if largest≠i18 19           then exchange A[i]↔A[largest]20 21                     MAX-HEAPIFY(A, largest)

2、建堆。BUILD-MAX-HEAP(A) 将数组按顺序简历完全二叉树，即二叉堆，对的长度等于数组长度。然后从i = n/2开始调用MAX-HEAPIFY(A, i)，i--，直到根(i==1)

代码：

1 BUILD-MAX-HEAP(A)2 3       heap-size[A] ← length[A]4 5      for i ← [lenth[A] / 2] downto 1    6 7           do MAX-HEAPIFY(A, i)

3、堆排序算法。HEAPSORT(A)进入循环，i=length(A).第一个节点和最后一个节点互换。堆的长度减一（即最后一个节点不参加排序，已经是排好序的以一个元素）。循环调用MAX-HEAPIFY(A, 1)， i减一（循环到i=2）。

代码： 

HEAPSORT（A)      BUILD-MAX-HEAP(A)     for i ← length[A] downto 2          do exchange A[1] ↔ A[i]               heap-size[A] ← heap-size[A]-1               MAX-HEAPIFY(A, 1)