二分木に対するヒープの唯一の利点は、二分木のO（log（2）n）ではなく、O（1）の複雑さでヒープ内の最小のアイテムを見つけることであるように思われます。
優先キューを実装するときは、データ構造からそれぞれ最小のアイテムを削除する必要があります。ツリーから最小のアイテムを削除し、両方のヒープをO（log（2）n）の複雑さで実行します。ツリーからアイテムを削除することは、より複雑な場合があります。子のないアイテムの削除は、実際には非常に簡単です。
私の質問は、優先キューを実装するときに、なぜバイナリツリー（この場合はより単純です）の代わりにヒープを使用するのですか？
二分木の場合の最悪の場合の複雑さは、二分木がヒープ内にある間に配列に収束するときにO（n）になり、O（log（n））のままになります。赤黒やAV1のようなバランスの取れた二分木を使用できますが、そうすると、より複雑になり、より多くのメモリが必要になります。
ヒープは通常、適切にバランスの取れた二分木よりも実装が簡単です。さらに、必要なメモリオーバーヘッドが少なく（要素はツリーノードやポインタなどすべてを割り当てることなく配列に直接格納できます）、パフォーマンスが向上する可能性があります（主に単一の連続した配列を使用するメモリの局所性による）...なぜ使ってみませんか？
最初の選択は、予想されるアクセスパターンと、保存する可能性のあるデータの量によって異なります。...
...ただし、オプションをできるだけ開いたままにして、少なくとも1つの選択肢のベンチマークを行い、パフォーマンスが向上した場合はそれに切り替えることができるようにすることをお勧めします。
過去20年間、私はヒープが何にでも最適な2つのアプリケーションにのみ取り組んできました（1回はLRUで、もう1回は厄介なオペレーションズリサーチアプリケーションで、ランダムに摂動されたk次元超立方体への加法性を復元します。ハイパーキューブ内のセルはk個の異なるヒープに表示され、メモリは貴重でした）。ただし、これら2つの場合、それらは代替案よりもはるかに優れたパフォーマンスを示しました。バランスの取れたツリーやbツリーよりも文字通り数十倍高速です。
前の段落で述べたハイパーキューブの問題について、私のチームリーダーは、赤黒木はヒープよりもパフォーマンスが優れていると考えていましたが、ベンチマークでは、赤黒木ははるかに遅いことが示されました（覚えているように、約20倍遅い） ）、そしてb-treeはかなり高速でしたが、ヒープもそれらを快適に打ち負かしました。
ヒープの重要な機能は、上記の両方の場合で、最小値のO（1）ルックアップではなく、ランダムに選択された要素のO（1）平均更新時間でした。
-James Barbetti（まあ、私はそうだと思っていました。しかし、キャプチャは私が人間ではないと言い続けています）
まず第一に、さまざまな二分木があり（それらのいくつかは非常に困難であり、それらのいくつかは平均しか提供しませんO(log n)）、ヒープはそれらの1つです。
2つ目：ほとんどのツリーでの操作はO(log n)複雑ですが、より複雑であり、一定の要因があります。
ヒープには一定の追加メモリが必要ですが、ツリーは通常、すべてのノードにポインタを格納する必要があります。
ちなみに、ヒープは非常に簡単で、配列のみを使用します（Javaでこのように実装されているかどうかはわかりませんが、そう思います）
検索または検索操作を頻繁に使用する場合は、平衡二分木が推奨されます。線分交差コードは、この1つの理由により、ヒープではなくバランスの取れたツリーを使用します。