问题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
我想确认,我是否正确地插入和删除堆,上面的回答是否正确? 如果不正确,请引导我。
你的答案看来是正确的。让我们仔细看看原因。
在第一种情况下,你有堆:
要插入97。所以你把它加到最后,然后把它泡起来:
你把97和它的父母(42)作比较。因为97更大,所以可以交换它们:
然后再将97与其父代进行比较。这次父母67岁了,所以你得再换一次。
再比较一次,您会发现父项(98)大于您插入的项,这样就完成了。
现在,给定堆
[100,97,93,38,67,54,93,17,25,42]
,您需要删除两个最高的项。delete_max的规则是用堆中的最后一项替换根,然后向下筛选。所以你有:42比它的子代小,所以您可以将它与最大的子代交换:
它大于38,但小于67,所以您再次交换:
而42现在是叶级,所以没什么可做的了。这是第一个被删除的项目。现在删除第二个。将25移到根:
然后筛选:
查找此链接,以便可以通过此链接访问
https://cstechwiki.blogspot.in/2016/09/python-week-6-quiz-assignment-nptel.html
相关问题 更多 >
编程相关推荐