什么是项目必须在一个删除的最大操作大小为N堆，没有重复的键来交换的最小数目？ [英] What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N with no duplicate keys?

问题描述

这个问题我在塞奇威克的书里读到了。而在他的网站，他说，答案是2，但我不明白怎么实现2，因为除去最大，我们首先需要交换的最大元素与最后一个，减少N，然后下沉最后一个从顶部向下到原来的位置，这需要交流logN个。那么，你是怎么做到2？

This question I came across in Sedgewick's book. And on his website, he says that the answer is 2, however I can't understand how to achieve 2, because to remove maximum we need to first exchange the max element with the last one, decrease N, and then sink the last one down from the top into its place, which takes logN exchanges. So, how do you achieve 2?

交流与放大器;删除-MAX：

Exchange & remove-max:

然后我们需要下沉，使L节点，这意味着我们需要做更多的logN个交流。

Then we need to sink, that L node, which means we need do logN more exchanges.

推荐答案

下面是15个节点的例子。我们的想法是：有根的儿子大（让左边较大），但对方左后代比是正确的要小得多。然后，你将只换了两次。

Here's an example for 15 nodes. The idea is: have the sons of the root be large (let the left one be larger), but the other left descendants be much smaller than the right ones. Then you will only swap twice.

                 100
       99                   90
   9       8            89      88
7    6   5   4        87   86   85   84

您会切换 84，100 然后 99，84 即可大功告成。两个互换。

You'll switch 84, 100 then 99, 84 and you're done. Two swaps.

有关 N'GT; 3 ，第一次交换后，有没有办法既没有根的两个儿子不会比新的根较大的（否则就不是一个堆开始）。所以，你必须做的是另交换。笔者最有可能的意思是写掉，而不是项目。

For n > 3, after the first swap, there is no way neither of the two sons of the root won't be larger than the new root (otherwise it wasn't a heap to begin with). So you'll have to do another swap. The author most likely meant to write swaps, not items.

这篇关于什么是项目必须在一个删除的最大操作大小为N堆，没有重复的键来交换的最小数目？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！