试图了解最大堆大小

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处的节点向下移动到最大堆，直到它不再违反max-heap属性（也就是说，该节点不小于其子节点。]

节点在正确位置之前可以走的最长路径等于节点的起始高度。每次节点需要在树中再下降一层时，该算法将精确选择要执行的一个分支，并且永远不会回溯。如果要堆的节点是最大堆的根，则它可以采用的最长路径是树的高度，即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-HEAPIFY O(n)次，因此构建整个堆是O(n log n)。*

_{*如评论中所述，可以显示更严格的O（n）上限。有关分析，请参见CLRS的第二版和第三版6.3节。 （我的第一版收拾好了，所以我无法验证部分号。）}

Answer 2

在最坏的情况下，是否不必反转每个节点？

您不必遍历每个节点。标准的max-heapify算法为：（摘自Wikipedia）

Max-Heapify (A, i):
    left ← 2*i  // ← means "assignment"
    right ← 2*i + 1
    largest ← i

    if left ≤ heap_length[A] and A[left] > A[largest] then:
        largest ← left
    if right ≤ heap_length[A] and A[right] > A[largest] then:
        largest ← right

    if largest ≠ i then:
        swap A[i] and A[largest]
    Max-Heapify(A, largest)

您可以看到，在每个递归调用上，您都停止或继续使用子树left或right。在后一种情况下，可以通过1降低树的高度。由于堆树根据定义是平衡的，因此您最多只能执行log(N)个步骤。