algorithm - 插入到最多一个交换的最大堆中

Question

是否有一种算法可以在最多一次交换的情况下执行插入到堆中（允许 O(log n) 比较）

Answer 1

不。

考虑这个堆：

假设您添加 200。显然它必须成为新的根。

那么100去哪儿了？它不能成为 3 岁的孩子，如果你只有一个交换，这就是它必须做的事情。