插入堆最多一个交换？

Question

Udi Manber的著名著作“算法导论”中有这样一个问题，即：

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

我想不出任何这样的算法，我甚至认为这是不可能的(就像您在最大堆中插入最大元素一样，它似乎无法工作)。有些答案甚至存在，说明这是impossible.But认为这个问题是一个好的来源，我再问一次，如果你能给一些好的想法，并找出作者想问的是什么？

Answer 1

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