[解決済み] ヒープを使いたいのはどんなとき?
2022-11-10 05:05:08
質問
優先度キューという明白な答えの他に、ヒープが私のプログラミングの冒険で役に立つのはどんなときでしょうか?
どのように解決するのですか?
最大(または最小)の項目に素早くアクセスする必要があるときはいつでもこれを使用します。その項目は常に配列の最初の要素、またはツリーのルートになるからです。
しかし、配列の残りの部分は部分的にソートされていない状態で保持されます。そのため、最大(最小)項目に対してのみ即時アクセスが可能です。 挿入は高速なので、イベントやデータの着信に対応し、常に最も早い/最も大きいものにアクセスできる良い方法です。
優先キュー、スケジューラ(最も早いアイテムが望まれる場合)などに有用です...
ヒープとは、親ノードの値がその子孫ノードの値よりも大きいツリーのことです。
ヒープを、ルートノードが最初にあり(次にそのノードの子、その次にそれらのノードの子)、深さによる線形順序で格納された二分木と考えるなら、インデックスNのノードの子は2N+1および2N+2にあります。 この性質により、インデックス単位での素早いアクセスが可能となる。 また、ヒープはノードの入れ替えによって操作されるため、インプレースソートが可能になります。
関連
-
[解決済み】最小スパニングツリー。カットプロパティとは何ですか?
-
[解決済み] 補助データ構造とは何ですか?
-
[解決済み] なぜバイナリサーチツリーでHashtableを実装するのか?
-
[解決済み] フュージョンツリーを理解する?
-
[解決済み] ヒープの構築はどうして時間計算量O(n)になるのですか?
-
[解決済み】2分木と2分探索木の違いについて
-
[解決済み] lenses, fclabels, data-accessor - 構造体アクセスと突然変異のためのどのライブラリが良いか
-
[解決済み] Clojureでリストが特定の値を含むかどうかをテストする
-
[解決済み] メモリ上でhexile/hexグリッドを表現するにはどうしたらよいですか?
-
[解決済み] ハッシュテーブルに対するバイナリサーチツリーの優位性
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み】最小スパニングツリー。カットプロパティとは何ですか?
-
[解決済み] 補助データ構造とは何ですか?
-
[解決済み] なぜバイナリサーチツリーでHashtableを実装するのか?
-
[解決済み] フュージョンツリーを理解する?
-
[解決済み】2分木と2分探索木の違いについて
-
[解決済み] lenses, fclabels, data-accessor - 構造体アクセスと突然変異のためのどのライブラリが良いか
-
[解決済み] Clojureでリストが特定の値を含むかどうかをテストする
-
[解決済み] メモリ上でhexile/hexグリッドを表現するにはどうしたらよいですか?
-
[解決済み] 二項探索木トラバーサル戦略(Preorder, Postorder, Inorder)をいつ使うか?
-
[解決済み] ハッシュテーブルに対するバイナリサーチツリーの優位性