過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

ヒープ

優先する値を根で取り出す

ヒープは、親子の間に一定の大小関係を持たせた木構造です。最小ヒープでは親の値が子以下で、根に最小値が置かれます。最大ヒープでは逆に根が最大値になります。典型的な二分ヒープは完全二分木の形を利用し、優先度付きキューやヒープソートに使われます。動的メモリー領域を指すヒープとは別の意味です。

配列で表す

根を添字0に置くと、節iの左の子を2i+1、右の子を2i+2に置く表現ができます。木の形が詰まっているため、節ごとに子への参照を持たずに位置を計算できます。ただし、子の添字が配列の長さ以上なら、その子は存在しません。式を使う前に添字の起点が0か1かを確認します。

追加と取出し

新しい要素は末尾へ置き、親との大小関係が崩れていれば上へ交換して調整します。根を取り出すときは末尾の要素を根へ移し、子との関係を見ながら下へ移動させます。標準的な二分ヒープでは木の高さが対数的なので、追加や根の取出しをO(log n)で行えます。根の値を見るだけなら全体を探索する必要はありません。

Pythonでの例

import heapq

priorities = [8, 3, 5, 1]
heapq.heapify(priorities)
heapq.heappush(priorities, 2)
first = heapq.heappop(priorities)
second = heapq.heappop(priorities)

最小ヒープの例なので、取り出されるのは順に1、2です。配列全体が昇順に並んでいるとは限りません。

探索木との違い

ヒープは親子の大小を保証しますが、左部分木の全てが右部分木より小さいとは限りません。任意の値を高速に探す二分探索木とは目的が違います。試験では、根が最優先であること、完全二分木の形、追加・削除後の調整を分けて確認します。優先度が同じときの順序まで保証したい場合は、追加の識別情報などを設計する必要があります。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

この用語に関連する問題

3問

用語一覧

4件