問題タブ [heap]

配列として格納されている 2 つの最大ヒープをマージするための効率的なアルゴリズムはありますか?

C スタイル言語でランタイム ヒープが動的メモリ割り当てに使用され、データ構造が両方とも「ヒープ」と呼ばれるのはなぜですか? 何か関係あるの？

heapq libsによって作成されたPythonヒープを覗く公式の方法は何ですか？今私は持っています

これは間違いなく、あまり良くありません。heap[0]それがヒープの一番上であると常に想定して使用できますか？それとも、基礎となる実装が多すぎると想定しますか？

ヒープとルート要素のリンクされた構造の実装で最も遠い要素を見つける方法を考えていました。要素を Enque および Deque できるようにしたい。

いくつかの明確化: 私が意味したのは、リンクされた構造が最大ヒープを構成しているとしましょう (ルート要素が最大の値を持っています)。ツリーの一番下のどこかに要素があり、エンキューしているかデキューしているかに応じて、後で挿入または削除します。その要素をどのように決定しますか？また、ツリーのルート ノードをどのように決定しますか? (一番上)

ヒープ構造を実装する場合、位置 i にあるノードの子が位置 2i および 2i+1 にあるように、データを配列に格納できます。

私の質問は、配列を使用して二分探索木を表現し、代わりにポインターなどを処理しないのはなぜですか?

ありがとう

私はこれに対する決定的な答えを見つけることができないようです、私はヒープでいくつかの初等的証明をしようとしていますが、これが私を少し遠ざけているものです：

空の木は有効ですか？もしそうなら、その高さは何ですか？
これは0になると思います。

単一ノードのツリーの高さはどれくらいですか？
これは1になると思いますが、0の定義を見てきました（この場合、空のツリーを説明する方法がわかりません）。

重複の可能性:
c# のフィボナッチ、バイナリ、または二項ヒープ?

.NET にヒープのようなクラスはありますか? 分を取得できるコレクションが必要です。エレメント。私はちょうど3つの方法が欲しい：

• Add()
• RemoveMinElement()
• GetMinElement()

キーは一意である必要があり、同じ要素がいくつかある可能性があるため、並べ替えられたリストは使用できません。

最小値と最大値の両方を効率的にポップする機能を除いて、stl（、、）のpush_heapようなアルゴリズムを探しています。AKAダブルエンド優先キュー。ここで説明されているように。pop_heapmake_heap

ダブルエンド優先キューのクリーンな実装も代替手段として重要ですが、この質問は主にMinMaxヒープの実装に関するものです。

私のグーグルフーは実りがありませんでした、しかし確かに、それは存在しなければなりませんか？

ヒープを作成するための Priority Queue インターフェイスを実装しました。その上にイテレータを実装する方法を教えてください。適切なチュートリアルを教えてください。私はJavaが初めてで、締め切りが非常に短いです。実際には、Object.id に基づいてヒープからオブジェクトを見つけて変更するメソッドが必要です。O(n) かどうかは気にしません。

// BinaryHeap クラス

キュー内のアイテムの優先度を変更できるプライオリティ キューを実装する必要があり、アイテムが常に正しい順序で削除されるようにキューが調整されます。これを実装する方法についていくつかのアイデアがありますが、これは非常に一般的なデータ構造であると確信しているので、私よりも賢い人による実装をベースとして使用できることを願っています.

このタイプのプライオリティ キューの名前を誰か教えてもらえますか?検索対象がわかるように、または実装を教えてもらえますか?