插入堆中最多一个交换？

有著名的书“算法导论”，由迪·曼伯，其中指出，插入堆中最多一个交换？

算法* Insert_To_Heap *可以换很多次了堆这个问题。修改算法，以便至多执行一次交换。 O（log n）比较仍然是允许的。

我想不出任何这样的算法，我甚至认为这是不可能的（好像你在最大堆插入的最大元素似乎并没有得到任何的工作方式）。有些答案甚至存在，这表明这是不可能的。但是考虑到这个问题来自一个很好的来源，我再次问是否有人可以给出一些好的想法，并找出作者想要问什么？

除非他使用了一些字眼技巧（“您可以将元素向下移动并在空白处插入新元素，不涉及交换”），但我没有看到任何方式来实现此目的。正如你所说，如果你插入一个新的最大值，那么当前的最大值必须在堆中向下移动一层，所以那里的元素也必须移动......这已经是2次移动（=掉期？）了。 –

这是一个很棒的“trick”这个词。可能是他试图问：P但是，如果我们插入最大元素，我们需要将根移到某个级别，如果两个根子项都被占用，那么班次将继续。 –

我们是在谈论一个普通的二进制堆吗？我似乎不可能。也许有些背景会对“一次交换”的含义有所帮助。我的意思是，从技术上讲，你可以重新构建整个堆而不用“交换”任何东西...... – mrip

我想如果我们使用二叉树来实现堆，并且每个子包含指向其父的指针，我们可以在一次插入操作和O（logN）比较操作中完成Insert_To_Heap。然而，这可能会生成一个只有一个孩子的节点，这会导致树更高。

2013-10-28 09:18:12 Guocheng

回答