尝试理解最大堆维护

Question

尝试理解最大堆维护

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的功能。它似乎是一个递归函数，但由于树的高度，它被称为在对数时间内运行。

对我来说，这毫无意义。在最坏的情况下，难道它不必反转每个节点吗？我不明白如何在不反复接触每个节点的情况下完成这项工作。

- DoubleBass

我使用CLRS这本书，其中MAX_HEAPIFY被明确说明为O(N)时间复杂度，这是一个简单的证明。你能告诉我视频的哪个部分表明它是O(log N)吗？ - Aravind

@Aravind 从26:06开始观看，并从那里继续观看。 - DoubleBass

@beaker：我把max_heapify和build_max_heap搞混了，我的错。 - Aravind

@Aravind 不用担心，在下面的评论中我混淆了max_heapify和insert。;) - beaker

3个回答

3

在最坏的情况下，它是否需要翻转每个节点？

您不必遍历每个节点。标准的“最大堆调整”算法如下（摘自维基百科）：

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)

从每次递归调用中你可以看到，你要么停止，要么继续遍历左节点或右节点的子树。在后一种情况下，你会将树的高度减少1。由于堆树是按照平衡的定义进行构建的，因此你最多需要进行 log(N) 步操作。

- sve

现在我更加困惑了，因为@Aravind说在CLRS中，它被展示为O（N）时间。 - DoubleBass

我给你一个随机列表 [7, 9, 8, 15, 13, 11, 10, 5, 6, 1, 14, 3, 2, 4, 12]，（第一层1个节点，第二层2个节点，第三层4个节点，第四层8个节点），你是说你可以在不触碰所有元素的情况下将其转换为最大堆？ - DoubleBass

@DoubleBass，您不必触及所有元素，只需触及从该元素首次添加的叶子到根之间的单个路径上的元素即可。正如CLRS所述，另一种思考方式是O(h)，其中h是树的高度。 - beaker

当我在列表上调用max_heapify时，结果列表似乎不是最大堆。 - DoubleBass

@DoubleBass 我已经添加了一个答案，因为它太长了，无法放在评论中。 - beaker

显示剩余2条评论

1

以下是关于为什么它是O(N)的一个论点。

假设它是一个完整的堆，因此每个非叶节点都有两个子节点。（即使不是这种情况，它仍然有效，但更麻烦。）

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

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

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

现在，假设我们有一个具有左右子堆的堆，并且MAX-HEAPIFY已经在两个子堆上运行过了。根据归纳假设，每个子堆都至少有一条从根到叶子节点上带有硬币的路径，因此我们至少有两条根到叶子节点上带有硬币的路径，每个子节点一条。为了确保MAX-HEAP属性，根节点需要完成的最远距离是交换直到树的底部。假设它向左子树进行了交换，并一直交换到底部。对于每次交换，我们需要花费一枚硬币，所以我们将其从根节点交换到的节点上花费了一枚硬币。

通过这样做，我们在其中一条根到叶子节点的路径上花费了所有的硬币，但请记住我们最初至少有两条这样的路径！因此，即使在整个堆上运行MAX-HEAPIFY后，我们仍然有一条完整的根到叶子节点带有硬币的路径。因此，MAX-HEAPIFY花费的硬币数量少于树中的节点数量。因此，交换的次数是O(N)。证毕。

- hjfreyer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- beaker · Accepted Answer

这是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节进行分析。（我的第一版被打包起来了，所以我无法验证章节号。）}