Udi Manber 著の有名な本「Introduction to Algorithms」には、次のような質問があります。
アルゴリズム *Insert_To_Heap* はヒープを何度もスワップする可能性があります。多くても 1 つのスワップが実行されるようにアルゴリズムを変更します。O(log n) の比較は引き続き許可されます。
私はそのようなアルゴリズムを考えることはできず、不可能だとさえ思います(最大要素を最大ヒープに挿入した場合、それはまったく機能しないようです)。これは不可能であると述べている回答もあります.しかし、この質問が良い情報源からのものであることを考えると、私はもう一度尋ねます.