如何将新值插入最大堆并将 max_delete 应用于堆

Question

问题 1

                     98
                    /  \
                   /    \
                 67      89
                / \     /  \
               /   \   /    \
             38   42  54    89
            / \
           /   \
          17   25

我想将 97 插入最大堆 [98,67,89,38,42,54,89,17,25]（在列表中表示）。

按照我的说法，结果堆是 [98,97,89,38,67,54,89,17,25,42]

                     98
                    /  \
                   /    \
                 97      89
                / \     /  \
               /   \   /    \
             38    67  54    89
            / \     |
           /   \    |
          17   25   42

问题 2

我想对堆 [100,97,93,38,67,54,93,17,25,42] 应用 delete_max() 两次。

                    100
                    /  \
                   /    \
                 97      93
                / \     /  \
               /   \   /    \
             38    67  54    93
            / \     |
           /   \    |
          17   25   42

根据两次 deletemax 操作后的堆，结果堆为 [93,67,93,38,42,54,25,17]

                     93
                    /  \
                   /    \
                 67      93
                / \     /  \
               /   \   /    \
             38    42  54    25
            /     
           /      
          17

我想符合，我是否正在做插入并且 max_delete 正确地用于堆和上面的答案是正确的？ 如果不正确，请指导我。

Answer 1

寻找这个 link 这样你就可以通过这个 link

访问

https://cstechwiki.blogspot.in/2016/09/python-week-6-quiz-assignment-nptel.html

Answer 2

您的回答看起来是正确的。让我们仔细看看为什么。

在第一种情况下，您有堆：

[98,67,89,38,42,54,89,17,25]

你想插入97，所以你把它加到最后，然后冒泡起来：

[98,67,89,38,42,54,89,17,25,97]

您将 97 与其 parent (42) 进行比较。因为 97 更大，所以你交换它们：

[98,67,89,38,97,54,89,17,25,42]

然后再次将 97 与其 parent 进行比较。这次 parent 是 67，所以你必须再次交换。

[98,97,89,38,67,54,89,17,25,42]

再比较一次，您发现 parent (98) 大于您插入的项目，所以您完成了。

现在，给定堆 [100,97,93,38,67,54,93,17,25,42]，您想要删除最高的两个项目。 delete_max 的规则是用堆上的最后一项替换根，然后筛选它。所以你有：

 [42,97,93,38,67,54,93,17,25]

42 比它的 children 小，所以你把它换成最大的 child:

 [97,42,93,38,67,54,93,17,25]

大于38，小于67，你再换：

 [97,67,93,38,42,54,93,17,25]

而 42 现在处于叶级别，因此无需再做任何事情。这是删除的第一项。现在删除第二个。将 25 移动到根：

 [25,67,93,38,42,54,93,17]

并筛选：

[93,67,25,38,42,54,93,17]  // swapped with 93
[93,67,93,38,42,54,25,17]  // swapped with 93 again

如何将新值插入最大堆并将 max_delete 应用于堆

how to insert new value into max heap and apply max_delete to heap

python

python-3.x

heap

heapsort

binary-heap