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

Question

问题1

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

我想将97插入max heap[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

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

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

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

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

我想确认，我是否正确地插入和删除堆，上面的回答是否正确？ 如果不正确，请引导我。

Answer 1

你的答案看来是正确的。让我们仔细看看原因。

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

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

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

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

你把97和它的父母（42）作比较。因为97更大，所以可以交换它们：

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

然后再将97与其父代进行比较。这次父母67岁了，所以你得再换一次。

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

再比较一次，您会发现父项（98）大于您插入的项，这样就完成了。

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

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

42比它的子代小，所以您可以将它与最大的子代交换：

 [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