ヒープと優先度付きキュー

優先度付きキューは、常に最も優先度の高い（または低い）要素を返す抽象データ型であり、ヒープは、効率的な挿入および最小値抽出操作でこれを実装する標準的なツリーベースの構造です。

Definition

優先度付きキューは、優先度を持つ要素の挿入と、最も優先度の高い要素の抽出をサポートする抽象データ型です。ヒープは、ヒープのプロパティ（各ノードのキーがその子ノードに対して一貫して順序付けられている）を満たすツリーベースのデータ構造であり、優先度付きキューを効率的に実装します。

Scope

このトピックでは、優先度付きキューADTとそのヒープ実装について扱います。具体的には、二分ヒープとその配列表現、ヒープのプロパティとsift-up/sift-down操作、ヒープソート、およびキー減少と結合コストを改善する二項ヒープやフィボナッチヒープなどの高度なマージ可能なヒープについて説明します。これは、優先度付きキューに依存するグラフアルゴリズム（ダイクストラ法、プリム法）やイベント駆動型シミュレーションに関連しています。

Core questions

• 優先度付きキューADTを定義する操作は何ですか、そしてヒープはそれらをどのように実装しますか？
• ヒープのプロパティは、定数時間での最小値検索と、対数時間での挿入/抽出をどのように可能にしますか？
• 二分ヒープは配列にどのようにコンパクトに格納され、線形時間でどのように構築されますか？
• ヒープソートはヒープを使用してO(n log n)時間でインプレースソートをどのように行いますか？
• フィボナッチヒープのようなマージ可能なヒープは、キーを頻繁に減少させるアルゴリズムをいつ改善しますか？

Key concepts

• 優先度付きキューADT
• ヒープのプロパティ
• 二分ヒープ
• 配列ベースのヒープ表現
• sift-upとsift-down
• 線形時間でのヒープ構築
• ヒープソート
• フィボナッチヒープと二項ヒープ

Key theories

ヒープのプロパティと配列表現

二分ヒープは、各ノードのキーがその子ノードのキーよりも優位であるほぼ完全な二分木であり、暗黙的な親子インデックスを持つ配列に格納できます。これにより、挿入と抽出はO(log n)、最小値検索はO(1)になります。

フィボナッチヒープの償却効率

フィボナッチヒープは、償却O(1)時間でのキー減少と償却O(log n)時間での最小値抽出をサポートし、多くのキー減少操作を実行するダイクストラ法やプリム法などのアルゴリズムの漸近的な実行時間を改善します。

Clinical relevance

優先度付きキューは不可欠なインフラストラクチャです。オペレーティングシステムのスケジューラで準備完了タスクを順序付けたり、離散イベントシミュレーションでイベントを管理したり、最良優先探索やA*探索を駆動したり、ダイクストラ法やプリム法でフロンティアを提供したりします。ヒープソートは、最悪の場合の保証された境界を持つO(n log n)のインプレースソートを提供します。

History

J. W. J. Williamsは1964年に二分ヒープとヒープソートを導入し、Robert Floydはその後すぐに線形時間のヒープ構築手順を発表しました。二項ヒープ（Vuillemin、1978年）とフィボナッチヒープ（FredmanとTarjan、1987年）は、効率的なマージと償却キー減少を追加し、古典的なグラフアルゴリズムの実行時間を改善しました。

Key figures

• J. W. J. Williams
• Robert W. Floyd
• Michael Fredman
• Robert Tarjan

Seminal works

• williams1964
• fredman1987
• cormen2009

Frequently asked questions

なぜ二分ヒープをポインタではなく配列に格納するのですか？

二分ヒープはほぼ完全な二分木であるため、そのノードは連続する配列インデックスにきれいにマッピングされます。インデックスiのノードは、2iと2i+1に子を持ちます。これにより、ポインタのオーバーヘッドが回避され、キャッシュの動作が改善され、ナビゲーションが単純な算術演算になります。

フィボナッチヒープはいつその複雑さに見合う価値がありますか？

フィボナッチヒープは償却O(1)のキー減少を提供し、密なグラフ上でのダイクストラ法の最短経路探索のようなアルゴリズムの漸近的な実行時間を改善します。実際には、その大きな定数係数により、より単純な二分ヒープの方が高速であることが多いため、主に理論的な境界や特殊なケースで重要となります。