algorithm - 试图了解 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 来完成此操作(叶子始终满足最大堆属性)。

来自 CLRS:

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

由于您调用 MAX-HEAPIFY O(n) 次，构建整个堆是 O(n log n)。*

_{* 如评论中所述，可以显示更严格的 O(n) 上限。参见 CLRS 第 2 版和第 3 版的第 6.3 节进行分析。 (我的第 1 版被打包了，所以我无法验证章节号。)}