试图理解 max heapify

Question

我试着看http://ocw.mit.edu/courses/electrical-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-HEAPIFY 将i处的节点沿最大堆向下移动，直到它不再违反最大堆属性（即该节点不小于其孩子们）。

一个节点到位前所能走的最长路径等于该节点的起始高度。每次节点需要在树中再下一级时，该算法都会选择一个分支来取，并且永远不会回溯。如果被堆化的节点是最大堆的根，那么它可以采用的最长路径是树的高度，或者O(log n)。

MAX-HEAPIFY 只移动一个节点。如果要将数组转换为最大堆，则必须在移至根之前确保所有子树都是最大堆。您可以通过在n/2节点上调用 MAX-HEAPIFY 来完成此操作（叶子始终满足 max-heap 属性）。

来自 CLRS：

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 版被打包带走，所以我无法验证章节编号。）}