問題タブ [binary-heap]

データ構造を定数空間のオーバーフロー バッファとして使用したいと考えています。効率的な挿入が必要ですが、最も重要なのは最小要素の効率的な削除です。O(log(n)) find_min() と log(n) の挿入と削除があるため、ヒープの使用を考えていました。一方、赤黒ツリーと比較して利点を理解していないことはわかっています。これは、O(log(n)) の挿入と削除もあり、O(1) で最小/最大が検出されるためです。そして、ソートされた出力の利点（私はそれについて気にしません）。

質問は関連しています:赤黒木は私の理想的なデータ構造ですか?

std::map と boost::heap から両方の構造を利用できるのに、赤黒ツリーの代わりにヒープを使用する必要があるのはなぜですか? 最後に、赤黒木を使用すると、エントリの検索時間も O(log(n)) になりますが、ヒープの場合、重複が存在するため重要な O(n) になります。

フォローアップ質問: https://codereview.stackexchange.com/questions/30243/how-can-i-improve-upon-my-a-pathfinding-code/

概要: 経路探索コード (A*) を改善するための支援を求めました。ユーザーは、私がノードの特定のリストを大量にソートしていること、および IComparible を使用してソートしていることにすぐに気付きました - どうやら非常に非効率的です。彼は OrderedBag を使用することを提案しましたが、すべてを自分でコーディングする必要があり、インターネットからのコードを使用することはできません。

質問:データをすばやく追加および削除できる一方で、バイナリ ヒープを作成することは、順序付けられたデータを維持する最も効果的な方法でしょうか。もしそうなら、誰かが私を正しい方向に向けて作成するためのリンクを持っていますか?

LinkedList について聞いたことがあります。

バイナリ ヒープを使用して PriorityQueue インターフェイスを実装する HeapPriorityQueue クラスを作成しようとしています。Java コレクションの PriorityQueue を使用しない場合。

HeapPriorityQueue クラスは、次のドライバー クラスによって実行されます。

プログラムの出力は次のようになります。

(1,1) (3,3) (5,5) (7,7) (9,9) (10,10)

これは私が作ってみたクラスです：

HeapPriorityQueue (参照)

コンソールのエラー行: 「スレッド "main" java.lang.Error での例外: 未解決のコンパイルの問題: タイプの不一致: HeapPriorityQueue から PriorityQueue に変換できません

誰でもこれを解決するのを手伝ってもらえますか?

2 つのヒープ配列を 1 つのバランスの取れたヒープ配列にマージし、線形の複雑さを維持するにはどうすればよいですか? ヒープのマージについて読んだ資料の多くは、O(nlogn) を使用します。

私のプログラムでは、一番上にない優先キューから要素を削除する必要があります。それはできますか？そうでない場合は、独自のヒープを作成する以外の方法を提案してください。