ヒープ（優先度キュー）の概念と基本操作

「やることがたくさんあるけれど、どれから手を付けるべき？」そんなとき、人は“優先度”で順番を決めます。

コンピュータの世界でも同じです。重要度の高いものから処理したいときに役立つのが、優先度キュー（Priority Queue）という考え方。そして、その優先度キューを効率よく支えるのがヒープというデータ構造です。
なぜヒープが便利なのか、Pythonでどう扱うのか、初心者の方にもわかりやすく丁寧に解説します。

ヒープとは？なぜ必要？

ヒープは「完全二分木」という形を持つデータ構造で、常に“親ノードが子ノードより小さい（または大きい）”というルールを守ります。このルールのおかげで、最小値（または最大値）を一瞬で取り出せます。 想像してみてください。タスク管理アプリで「締切が一番近いタスク」だけすぐ取り出したいとき。毎回すべてを並べ替えるのは大変ですが、ヒープなら先頭だけは必ず最小（または最大）なのでサッと取り出せます。

ここで覚えておきたい2つのタイプがあります。

• 最大ヒープ: 親 ≥ 子（親が常に最大に近い）
• 最小ヒープ: 親 ≤ 子（親が常に最小に近い）

Pythonでは最小ヒープが基本です。つまり、先頭には「最小の値」が来ます。優先度の高いものを先に処理したいなら、優先度を「小さいほど高い」として扱うイメージです。

ヒープでできる基本操作を流れで理解する

ヒープを使うと、次のような操作が効率よく行えます。ここでは、最小ヒープを例に、処理の流れをイメージしながら理解しましょう。

まず「挿入」です。新しい値を配列の末尾に追加し、そこから親と比較して“上に向かって”入れ替えていきます（これを heapify up と呼びます）。最終的にヒープのルール（親 ≤ 子）が守られるところで止まります。

次に「取得（最小値の参照）」では、先頭（ルート）を見るだけです。これは配列の先頭要素なので、ほぼ一定時間で完了します。

「削除（最小値の削除）」は少しだけ工夫が必要です。ルートの値を取り出したら、末尾の要素をルートに移動します。するとルールが壊れますから、今度は“下に向かって”正しい位置まで入れ替えていきます（これが heapify down です）。

これらの操作はとても高速です。挿入と削除は O(log n)、最小値の参照は O(1) 程度の時間でできます。大量のデータを扱うときに、毎回ソートし直すより圧倒的に速いのがヒープの魅力です。

Pythonで最小ヒープを実装してみる

ここからは、最小ヒープをクラスとして自前実装してみます。内部ではリストを使い、heapify up / down でヒープの性質を保ちます。

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def delete_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        min_value = self.heap[0]
        self.heap[0] = self.heap.pop()  # 最後の要素をルートに移動
        self._heapify_down(0)
        return min_value

    def get_min(self):
        return self.heap[0] if self.heap else None

    def _heapify_up(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] < self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            self._heapify_up(parent_index)

    def _heapify_down(self, index):
        smallest = index
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2

        if left_child_index < len(self.heap) and self.heap[left_child_index] < self.heap[smallest]:
            smallest = left_child_index

        if right_child_index < len(self.heap) and self.heap[right_child_index] < self.heap[smallest]:
            smallest = right_child_index

        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._heapify_down(smallest)

    def __str__(self):
        return str(self.heap)

まず、コンストラクタの __init__ では空のリストを用意します。ここがヒープの実体です。最初は中身がないので、挿入された順に要素が増えていきます。

insert は新しい値を配列の末尾に追加したあと、_heapify_up を呼び出して正しい位置まで親と入れ替えていきます。追加直後はルールが崩れていても、上へ上へと移動していくうちに、最小ヒープの性質（親 ≤ 子）が回復します。

最小値を取り除く delete_min は、からのときは None を返します。要素が1つだけならそれを返して終わりです。複数ある場合は、先頭（最小値）を取り出し、配列の末尾の要素を先頭に移動します。その結果、ヒープの条件が壊れるので、_heapify_down を使って子のほうへ値を下げながら正しい位置を探します。これで、先頭に最小値が来るというヒープの性質が再び整います。

get_min はとてもシンプルで、ヒープが空でなければ先頭の値を返します。最小ヒープではここが常に最小値です。空なら None を返すので、呼び出し前に空チェックを意識すると安心です。

_heapify_up は挿入時に使われる補助メソッドです。自分と親を比べて、自分のほうが小さければ入れ替えます。入れ替えたら、今度は親の位置で同じ確認を繰り返します。こうして、要素は正しい場所まで一段ずつ上がっていきます。

_heapify_down は削除後などに使う補助メソッドです。自分の左右の子のうち、より小さいほうと比較して、もし自分のほうが大きければ入れ替えます。その後、入れ替えた先でまた同じ処理を繰り返します。これにより、大きすぎる値がだんだん下に降りていき、親 ≤ 子 の関係が守られます。

最後に __str__ はヒープの内部リストをわかりやすく文字列化します。学習中に状態を確認したいときに便利です。

以下のような例で、挙動を確認してみましょう。動かしてみると、最小値が常に先頭に来ることが直感的に理解できます。

#上記コードの続き
heap = MinHeap()
heap.insert(10)
heap.insert(4)
heap.insert(15)
heap.insert(20)
heap.insert(3)

print("Heap:", heap)

print("Minimum value:", heap.get_min())
print("Deleting minimum value:", heap.delete_min())
print("Heap after deletion:", heap)

このコードでは、まず 10, 4, 15, 20, 3 の順に数値を挿入しています。内部では毎回 heapify up が走り、先頭に最小値が来るよう整えられます。get_min() で最小値を確認すると 3 が返り、delete_min() で 3 を取り除いたあとも、残りの要素が最小ヒープの形に保たれているのがわかります。

ヒープの計算量と使いどころを整理しよう

ここまでの内容を、実行時間の観点からまとめておきます。

• 挿入（heappush / insert）は O(log n)。木の高さぶんだけ比較と入れ替えをします。
• 最小値の参照（先頭を見る）は O(1)。配列の先頭を見るだけです。
• 最小値の削除（heappop / delete_min）は O(log n)。
• リストからまとめてヒープ化（heapify）は O(n)。大量データの初期化に有利です。

ヒープは、ジョブのスケジューリング、Dijkstra法などのグラフ最短経路、K個の最小/最大要素の抽出、リアルタイム優先度処理（例: イベント駆動、ログの上位N件）など、幅広い場面で役立ちます。

まとめ

ヒープ（優先度キュー）は、「最も重要なものをすぐ取り出したい」という日常的なニーズを高速に満たすデータ構造です。完全二分木の形と、親 ≤ 子（または親 ≥ 子）のルールを守ることで、最小（最大）の取得・削除・挿入を効率化します。Pythonでは自作実装で仕組みを理解しつつ、実務では heapq を活用するのが現実的です。

次の学習では、ヒープを使ったアルゴリズム（例えば最短経路探索）に挑戦したり、再帰やソートとの関係を比較して理解を深めていきましょう。優先度という現実的な視点をプログラムに取り入れられるようになると、コードの表現力が一段と広がります。