0

在 Udi Manber 的名著《算法导论》中有这个问题,它指出

算法 *Insert_To_Heap* 可能会在堆上多次交换。修改算法,以便最多执行一次交换。仍然允许 O(log n) 比较。

我想不出任何这样的算法,我什至认为这是不可能的(好像你在最大堆中插入了最大元素,它似乎并没有以任何方式工作)。甚至存在一些答案,表明这是不可能的。但是考虑到这个问题的来源很好,我再次问你是否可以提出一些好的想法并找出作者试图问的问题?

4

1 回答 1

0

我认为如果我们使用二叉树来实现堆,并且每个子节点都包含指向其父节点的指针,我们可以在一次插入操作和 O(logN) 比较操作中完成 Insert_To_Heap。但是,这可能会生成一个只有一个子节点的节点,这将导致一棵更高的树。

于 2013-10-28T09:18:12.187 回答