二分ヒープとは？優先度付きキュー・コード・計算量を解説

ヒープが解決する問題

多くのプログラムは、変化し続けるコレクションから、最も緊急の要素を繰り返し取り出す必要があります。シミュレーションの次のイベント、ダイクストラ法で最も近い未訪問ノード、最も優先度の高いタスク、ストリーム中のk個の最大値などです。挿入のたびにコレクション全体をソートし直すと、毎回O(n log n)かかります。ソート済みリストなら取り出しは安くなりますが、挿入がO(n)です。ヒープなら、挿入も最小値の取り出しもO(log n)で、これはまさに優先度付きキューが必要とする性能です。

考え方：配列に格納された木

ヒープは完全二分木です。最後のレベルを除いてすべてのレベルが埋まっており、最後のレベルは左から詰められます。この形のおかげで、ポインタなしで、ふつうのリストに木を格納できます。

ヒープ条件を保つ修復操作は2つあります。sift up：新しい要素を末尾に追加したあと、親より小さい間、親と入れ替えていきます。sift down：最後の要素を根に移したあと、小さいほうの子より大きい間、その子と入れ替えていきます。どちらの操作も根から葉への1本の経路をたどるので、入れ替えは多くても約log2(n)回です。

具体例：pushとpop

最小ヒープ[2, 5, 3, 9, 6]から始めます（2が根で、その子が5と3、5の子が9と6です）。

1. 1をpush：末尾に追加して[2, 5, 3, 9, 6, 1]になります。インデックス5の親はインデックス2（値3）です。
2. 1は3より小さいので入れ替えて[2, 5, 1, 9, 6, 3]になります。次に、インデックス2の親はインデックス0（値2）です。
3. 1は2より小さいので入れ替えて[1, 5, 2, 9, 6, 3]になります。根に着いたので終了です。
4. pop：根の1を取り除き、最後の要素3を根に移します：[3, 5, 2, 9, 6]。
5. 根の子は5と2で、小さいほうは2です。3のほうが大きいので入れ替えて[2, 5, 3, 9, 6]になります。インデックス2には子がないので終了です。popは1を返しました。

Pythonでの最小ヒープの実装

このクラスは仕組みを示すためのものです。実際のコードでは、次のセクションで示すheapqを使います。

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[i] < a[(i - 1) // 2]:      # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p
    def pop(self):
        a = self.a
        top, last = a[0], a.pop()                   # IndexError if empty
        if a:
            a[0], i = last, 0
            while True:                             # sift down
                c = 2 * i + 1
                if c + 1 < len(a) and a[c + 1] < a[c]:
                    c += 1                          # pick the smaller child
                if c >= len(a) or a[i] <= a[c]:
                    break
                a[i], a[c] = a[c], a[i]
                i = c
        return top
h = MinHeap()
for x in [5, 3, 9, 1, 6, 2]:
    h.push(x)
print([h.pop() for _ in range(6)])  # [1, 2, 3, 5, 6, 9]

Pythonのheapqによる優先度付きキュー

heapqモジュールは通常のリストに対して働き、常に最小ヒープとして保ちます。heapifyは、既存のリストをその場でO(n)でヒープに変換します。優先度を使うには、タプルをpushします。Pythonはタプルを要素ごとに比較するので、先頭の要素が優先度になります。優先度が等しい要素どうしを直接比較せずに済むように、タイブレーク用のカウンタを加えます。

import heapq
from itertools import count
nums = [7, 2, 9, 4, 1]
heapq.heapify(nums)
print(nums[0], heapq.heappop(nums))      # 1 1
print(heapq.nlargest(2, [7, 2, 9, 4]))   # [9, 7]
tasks, order = [], count()
heapq.heappush(tasks, (2, next(order), "write report"))
heapq.heappush(tasks, (1, next(order), "fix outage"))
heapq.heappush(tasks, (2, next(order), "reply to email"))
while tasks:
    priority, _, name = heapq.heappop(tasks)
    print(priority, name)
# 1 fix outage
# 2 write report
# 2 reply to email

最大ヒープについては、Python 3.14でheapq.heapify_max、heapq.heappush_max、heapq.heappop_maxが追加されました。それより古いバージョンでは、キーの符号を反転してpush（たとえばheapq.heappush(h, -score)）し、popしたときにもう一度符号を反転するのが定番の手です。

時間計算量と空間計算量

pushをn回呼んでヒープを作るとO(n log n)かかります。heapifyは最後の親から根に向かってsift downするので、O(n)です。すべての要素が手元にあるなら、こちらを選びましょう。

種類と、よくある間違い

• 最大ヒープ：比較を逆にしただけの同じコードです。Pythonでは、_max関数（3.14以降）を使うか、キーの符号を反転します。
• d分ヒープ：各ノードがd個の子を持ちます。木が浅くなるので、pushは安くなり、popはやや高くなります。
• インデックス付き優先度付きキュー / decrease-key：heapqでは、要素の優先度をその場で変更できません。よく使われる回避策（ダイクストラ法で使われます）は、新しいエントリをpushし、古くなったエントリはpopされたときに読み飛ばすことです。
• 比較できない要素を比較する：(priority, dict)をpushすると、2つの優先度が等しいときに、Pythonがdict同士を比較するためTypeErrorになります。タプルの2番目の要素にカウンタを加えましょう。
• ヒープのリストがソート済みだと思い込む。保証されているのはheap[0]だけです。すべてを順に取り出したいならsorted(heap)を使います。
• 教科書の1始まりの式（子は2iと2i + 1）と、0始まりのPythonのリストを混ぜて、1つずれる間違いをする。

ヒープを使う場面と、典型的な問題

変化し続けるコレクションから、最小または最大の要素だけを繰り返し取り出したいときに、ヒープを使います。順序付きの反復や任意の削除も必要ならソート済みリストか平衡木を、最小値が1回だけ必要なら素のmin()を使います。

定番の用途：ダイクストラ法による最短経路とPrim法による最小全域木、k個のソート済みリストのマージ（heapq.merge）、k個の最大または最小の要素の発見（サイズkのヒープを保つ、O(n log k)）、移動中央値（2つのヒープ）、タスクスケジューラとイベント駆動のシミュレーション、ヒープソートなどです。