データ構造を定数空間のオーバーフロー バッファとして使用したいと考えています。効率的な挿入が必要ですが、最も重要なのは最小要素の効率的な削除です。O(log(n)) find_min() と log(n) の挿入と削除があるため、ヒープの使用を考えていました。一方、赤黒ツリーと比較して利点を理解していないことはわかっています。これは、O(log(n)) の挿入と削除もあり、O(1) で最小/最大が検出されるためです。そして、ソートされた出力の利点（私はそれについて気にしません）。
質問は関連しています:赤黒木は私の理想的なデータ構造ですか?
std::map と boost::heap から両方の構造を利用できるのに、赤黒ツリーの代わりにヒープを使用する必要があるのはなぜですか? 最後に、赤黒木を使用すると、エントリの検索時間も O(log(n)) になりますが、ヒープの場合、重複が存在するため重要な O(n) になります。
違いは、主に構造の使用方法にあります。
バイナリ ヒープは、値を挿入して最小値を取得するための非常に高速なデータ構造です。ただし、ランダム値の効率的な検索や削除はサポートされていません。
赤/黒ツリーは、効率的な挿入、削除、任意の値のルックアップ、および (適度に高速な) 検索最小値をサポートするバランスのとれた二分探索ツリーです。ただし、バイナリ ヒープに比べて多くのオーバーヘッドがあります。
挿入、最小検索、および最小削除だけが必要な場合は、オーバーヘッドが低く、ランタイムが高速であるため、バイナリ ヒープがおそらく優れた選択肢です。任意の値を挿入および削除したり、任意の値を参照したりする必要がある場合は、おそらく赤/黒ツリーが適切な選択です。すべてのエンジニアリングと同様に、適切なデータ構造を選択するにはトレードオフがすべてです。
std::priority_queueまた、バイナリ ヒープが必要な場合に使用できることに注意してください。Boost を使用する必要はありません。またstd::map、赤/黒のツリーであるとは限りません。おそらく何らかのバランスの取れた BST ですが、他のアルゴリズムを使用してバランスを取ることもできます。
お役に立てれば！
ヒープは、連続したメモリ、つまり配列に簡単に実装できます。赤黒木は通常、各ノードに個別のヒープを割り当てて構築されます。レッド ブラック ツリーは、各ツリー トラバーサルでヒープ全体のメモリにアクセスすることになります。これは最悪の場合のキャッシュ動作です。特定の操作のアルゴリズムの複雑さは両方の構造で同じですが、赤黒ツリーの一定のオーバーヘッドははるかに高くなります。