用語集 › 💻 プログラミング › ヒープ（データ構造）
【ひーぷ】

ヒープ（データ構造） とは？

最終更新:
💡 「最大値・最小値」を常に一番上にキープする木構造
📌 このページのポイント
最大ヒープ（Max-Heap） 100 80 70 50 60 30 20 ← ルート = 最大値 親 ≧ 子 配列表現: 100 80 70 50 60 30 20 [0] [1] [2] [3] [4] [5] [6]
最大ヒープの二分木構造と配列表現
ひよこ ひよこ
ソート済み配列で最大値を取るのと何が違う？
ペンギン先生 ペンギン先生
ソート済み配列は最大値の取得がO(1)だけど、挿入がO(n)かかる。ヒープは挿入も削除もO(log n)で、最大/最小値の取得がO(1)。データが動的に追加・削除される場面ではヒープの方が効率的。毎回ソートし直すよりずっと速いんだよ
ひよこ ひよこ
優先度付きキューって何？
ペンギン先生 ペンギン先生
通常のキューはFIFO（先入れ先出し）だけど、優先度付きキューは「優先度が高いものから出てくる」。ER（救急外来）の患者対応みたいなもので、到着順ではなく重症度順。内部実装にヒープを使うと、追加O(log n)・取り出しO(log n)・最高優先度の確認O(1)で効率的なんだよ
ひよこ ひよこ
配列でどうやって木を表現するの？
ペンギン先生 ペンギン先生
完全二分木は配列のインデックスで親子関係を表現できる。インデックスiのノードの左の子は2i+1、右の子は2i+2、親は(i-1)/2（切り捨て）。ポインタが不要でキャッシュ効率も良い。挿入は配列末尾に追加してから親と比較しながら上に移動（swim up）、削除はルートと末尾を入れ替えてから下に沈める（sink down）んだよ
ひよこ ひよこ
実務でヒープを直接使う場面は？
ペンギン先生 ペンギン先生
Pythonのheapq、JavaのPriorityQueue、C++のpriority_queueがヒープの標準実装。①ダイクストラ法（最短経路）の「次に処理するノード」の管理、②ストリームデータからTop-K（上位K件）の取得、③タスクスケジューラの実装、④マージソートの外部ソート。競技プログラミングでは頻出だし、実務でもライブラリ経由でよく使っているんだよ
ペンギン
まとめ：ざっくりこれだけ覚えればOK！
「ヒープ」って出てきたら「最大値か最小値を効率よく取り出せる木のデータ構造」と思えればだいたいOK！
📖 おまけ：英語の意味
「Heap」 ＝ 山積み
💬 Heap（積み上げたもの）。一番上に最大/最小の要素が積まれているイメージだよ
🔗 あわせて読みたい
← 用語集にもどる