在 Udi Manber 的名著《算法导论》中有这个问题,它指出
算法 *Insert_To_Heap* 可能会在堆上多次交换。修改算法,以便最多执行一次交换。仍然允许 O(log n) 比较。
我想不出任何这样的算法,我什至认为这是不可能的(好像你在最大堆中插入了最大元素,它似乎并没有以任何方式工作)。甚至存在一些答案,表明这是不可能的。但是考虑到这个问题的来源很好,我再次问你是否可以提出一些好的想法并找出作者试图问的问题?
在 Udi Manber 的名著《算法导论》中有这个问题,它指出
算法 *Insert_To_Heap* 可能会在堆上多次交换。修改算法,以便最多执行一次交换。仍然允许 O(log n) 比较。
我想不出任何这样的算法,我什至认为这是不可能的(好像你在最大堆中插入了最大元素,它似乎并没有以任何方式工作)。甚至存在一些答案,表明这是不可能的。但是考虑到这个问题的来源很好,我再次问你是否可以提出一些好的想法并找出作者试图问的问题?