试图理解最大堆化

Question

我试着看http://ocw.mit.edu/courses/electrice-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/来理解堆和堆排序，但没有发现这一点。

我不明白max-heapify的功能。它看起来像是一个递归函数，但由于树的高度，它会以对数时间运行。

对我来说这毫无意义。在最坏的情况下，它不是要逆转每一个单个节点吗？我看不出如何做到这一点，不让它反复地触及每一个节点。

Answer 1

以下是MAX-HEAPIFY的功能：

给定索引i处的一个节点，其左、右子树都是max-heaps，MAX-HEAPIFY将i处的节点向下移动max-heap直到它不再违反max-heap属性（即节点不小于它的子节点）。

一个节点在其处于适当位置之前所能走的最长路径等于该节点的起始高度。每当节点需要在树中再往下走一层时，算法就会恰好选择一个分支采取，并且绝不会回溯。如果被堆化的节点是max-heap的根，那么它可以采取的最长路径是树的高度，或者o(logn)。

for i = floor(length(A)/2) downto 1
   do MAX-HEAPIFY(A,i)

由于调用MAX-HEAPIFYO(n)次，因此构建整个堆的时间为O(n log n).*

_{*如注释中所述，可以显示O(n)的一个更紧的上界。有关分析，请参见CLRS第2版和第3版的第6.3节。（我的第1版已经打包好了，所以我无法验证节号。）}