6

我试着看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 的功能。它似乎是一个递归函数，但由于树的高度，它以某种方式运行在对数时间内。

对我来说这毫无意义。在最坏的情况下，它是否必须反转每个节点？如果不反复触及每个节点，我不明白如何做到这一点。

4

3 回答 3

8

以下是 MAX-HEAPIFY 的作用：

给定索引i处的节点，其左右子树都是最大堆，MAX-HEAPIFY 将i处的节点沿最大堆向下移动，直到它不再违反最大堆属性（即节点不小于其孩子们）。

一个节点在它处于正确位置之前可以走的最长路径等于该节点的起始高度。每次节点需要在树中再向下一层时，算法将准确选择一个分支，并且永远不会回溯。如果被堆化的节点是最大堆的根，那么它可以走的最长路径就是树的高度，或者O(log n).

MAX-HEAPIFY 只移动一个节点。如果要将数组转换为最大堆，则必须确保所有子树都是最大堆，然后再转到根。您可以通过在节点上调用 MAX-HEAPIFY 来做到这一点n/2（叶子总是满足最大堆属性）。

来自 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 节。（我的第一版被打包了，所以我无法验证章节号。）

于 2016-01-28T03:32:16.073 回答
3

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

您不必遍历每个节点。标准max-heapify算法是：（取自维基百科）

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)步骤。

于 2016-01-28T01:35:27.010 回答
0

这是为什么它是 O(N) 的一个论点。

假设它是一个完整的堆，所以每个非叶节点都有两个孩子。（即使不是这样，它仍然有效，但更烦人。）

将硬币放在树中的每个节点上。每次我们进行交换时，我们都会花费其中一个硬币。（请注意，当元素在堆中交换时，硬币不会与它们交换。）如果我们运行 MAX-HEAPIFY，并且有剩余的硬币，这意味着我们进行的交换比树中的节点少，因此 MAX-HEAPIFY 执行 O(N) 交换。

声明：在 MAX-HEAPIFY 运行完成后，堆总是有至少一条从根到叶的路径，路径的每个节点上都有硬币。

归纳证明：对于单节点堆，我们不需要做任何交换，所以我们不需要花费任何硬币。因此，一个节点可以保留其硬币，并且我们有一条从根到叶（长度为 1）的完整路径，硬币完好无损。

现在，假设我们有一个带有左右子堆的堆，并且 MAX-HEAPIFY 已经在两者上运行。通过归纳假设，每个都有至少一条从根到叶的路径，上面有硬币，所以我们至少有两条从根到叶的有硬币的路径，每个孩子一个。为了建立 MAX-HEAP 属性，根需要走的最远距离是一直交换到树的底部。假设它向下交换到左子树，并且一直向下交换到底部。对于每次交换，我们需要花费硬币，所以我们从根交换到的节点花费它。

在此过程中，我们将所有硬币都花在了从根到叶的路径之一上，但请记住，我们最初至少有两个！因此，在整个堆上运行 MAX-HEAPIFY 后，我们仍然有一条完整的从根到叶的路径。因此，MAX-HEAPIFY 花费的硬币比树中的节点少。因此，交换次数为 O(N)。QED。

于 2021-02-11T21:24:54.017 回答