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

2024-05-08 02:11:05 发布

您现在位置:Python中文网/ 问答频道 /正文

问题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      

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


Tags: 列表deletemaxheapmedeletemax
2条回答

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

在第一种情况下,你有堆:

[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

相关问题 更多 >