algorithm - 最多在一次交换中插入堆？

Question

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

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

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

Answer 1

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