本文共 935 字，大约阅读时间需要 3 分钟。

MAX-HEAPIFY(A, i) 	l <- LEFT(i)	r <- RIGHT(i)	if l <= heap-size[A] and A[l] > A[i]		then largest <- l		else largest <- i	if r <= heap-size[A] and A[r] > A[largest]		then largest <- r	if largest != i		then exchange A[i] <-> A[largest]			MAX-HEAPIFY(A,largest)

**************************************

**************************************

1. 参数A是二叉堆数组，参数i是某个子堆的顶节点，i节点的左右子堆满足堆性质，但i节点可能不满足堆性质。

2. 获取i节点的左孩子对应于数组A的下标索引l 3. 获取i节点的右孩子对应的数组A的下标索引r 4. 如果l（即i节点的左孩子在数组A中的下标索引）没有超出二叉堆的范围（heap-size[A]），而且索引l对应的节点的值大于节点i的值 5. 那么，largest存储较大的索引节点，依照第4行的判断，如果左孩子的值大于节点i的值，则存储到下标索引（l）到largest 6. 否则，则存储节点i下标索引（i）到largest，这时，largest中保存的是i节点和i节点的左孩子中较大值的下标索引 7. 同第4行，开始比较i节点的右孩子，同样需要判断是否已经超出了堆的有效长度，这时候和右孩子的值进行比较的是largest，因为largest所对应的值，是i节点和左孩子中的较大值。 8. 如果A[r]的值大于A[largest]，那么把r存储到largest，这时候就保证了largest中保存的是节点i和其左右孩子的最大值的下标索引。 9. 如果i节点不是最大节点 10. 那么，交换i节点和largest索引对应的值 11.交换后，可能破坏堆性质，递归调用MAX-HEAPIFY，递归调用后，树向下转移一层，递归调用的终结条件为l和r超出了heap-size[A]的有效长度。

转载地址：http://voyni.baihongyu.com/