algorithm - 最大 1 つのスワップによる最大ヒープへの挿入

Question

最大 1 つのスワップでヒープへの挿入を実行するアルゴリズムはありますか (O(log n) の比較が許可されます)

Answer 1

いいえ。

このヒープを考えてみましょう:

200 を追加するとします。明らかに、それが新しいルートになる必要があります。

では、100 はどこに行くのでしょうか。3 の子になることはできません。これは、スワップが 1 つしかない場合に行う必要があることです。