0

Udi Manber 著の有名な本「Introduction to Algorithms」には、次のような質問があります。

アルゴリズム *Insert_To_Heap* はヒープを何度もスワップする可能性があります。多くても 1 つのスワップが実行されるようにアルゴリズムを変更します。O(log n) の比較は引き続き許可されます。

私はそのようなアルゴリズムを考えることはできず、不可能だとさえ思います(最大要素を最大ヒープに挿入した場合、それはまったく機能しないようです)。これは不可能であると述べている回答もあります.しかし、この質問が良い情報源からのものであることを考えると、私はもう一度尋ねます.

4

1 に答える 1

0

二分木を使用してヒープを実装し、すべての子にその親へのポインターが含まれている場合、たった 1 回の挿入操作と O(logN) の比較操作で Insert_To_Heap を完了することができると思います。ただし、これにより、子が 1 つしかないノードが生成され、ツリーが高くなる可能性があります。

于 2013-10-28T09:18:12.187 に答える