【ひーぷ】

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

最終更新: 2026年10月4日

💡 「最大値・最小値」を常に一番上にキープする木構造

親子の間で値の大小関係を保つ木のデータ構造。代表的な二分ヒープは完全二分木を使い、最大値か最小値が根に来るようにする。優先度付きキューの実装に使われる。

📌 このページのポイント

同じ完全二分木を配列で表した例です。線は親子関係で、データの移動ではありません。親は子以上ですが、配列全体が大きい順に並ぶ必要はありません。

ひよこ

ソート済み配列と何が違うの？

ペンギン先生

ヒープは全体を順番に並べず、親子の大小関係を保つよ。最大ヒープなら根が最大値で、同じ値も入る。図の配列では50の次に60があるように、根以外まで大きい順になるとは限らないんだ

ひよこ

追加や取り出しは速い？

ペンギン先生

二分ヒープでは、挿入や根を取り出した後の整列調整にO(log n)、根の値を見るだけならO(1)かかるよ。配列を拡張するときのコピーは別に必要で、サイズを増減する実装では挿入・根の取り出しをならしてO(log n)と評価するんだ

ひよこ

好きな値を探して削除するのもO(log n)？

ペンギン先生

その値がどこにあるかを探す処理は別だよ。普通のヒープを順に調べれば、最悪O(n)かかる。削除対象の位置を管理する仕組みを加える実装もあるけれど、根の取り出しと任意要素の検索を混同しないでね

ひよこ

配列でどうやって木を表すの？

ペンギン先生

完全二分木を上から、各段の左から順に配列へ置くよ。添字が0始まりなら、i番目の子は2i+1と2i+2で、その添字が配列の範囲内にある場合だけ存在する。根以外の親は(i-1)/2の切り捨てだね

ひよこ

どんな場面で使うの？

ペンギン先生

優先度が高い仕事から取り出す優先度付きキューなどに使うよ。Pythonのheapqは通常、最小値を根にする二分ヒープで、配列から作るheapifyはO(n)。値の小ささを優先度に対応させれば、次の仕事を効率よく選べるね

まとめ：ざっくりこれだけ覚えればOK！

「ヒープ」って出てきたら「最大値か最小値を効率よく取り出せる木のデータ構造」と思えればだいたいOK！

📖 おまけ：英語の意味

「Heap」＝山積み

💬 Heap（積み上げたもの）。一番上に最大/最小の要素が積まれているイメージだよ

参考資料