【heapq】Pythonで優先度付きキューを扱う方法を解説

Python

本記事では、Pythonの標準モジュールheapqを使って優先度付きキューを効率的に扱う方法を解説します。heapqを利用すれば、最小ヒープを簡単に実装し、優先度に応じた要素の管理や取り出しを効率的に行えます。

優先度付きキューとは

優先度付きキューは、各要素に優先度が設定されており、通常のキュー（FIFO: 先入れ先出し）とは異なり、優先度の高い要素が先に取り出されるデータ構造です。

特徴

  1. 要素ごとに優先度がある
    • 各要素は「値」と「優先度」を持ち、優先度が高いものが先に取り出される。
  2. 通常のキューと異なり、FIFOではなく優先度順
    • 例えば、通常のキューでは A → B → C の順で入れたら、そのまま A → B → C の順で取り出される。
    • 優先度付きキューでは、優先度が高い C を先に取り出す場合がある。
  3. 内部実装にはヒープがよく使われる （ヒープとは、各親ノードがどの子ノードよりも小さいか等しい値を持つ二分木のこと）
    • 最小ヒープ（Min Heap）: 優先度が最小の要素が先に取り出される。これにより、常に「最小の値」が根（root）に位置し、最優先で取り出すことができる。
    • 最大ヒープ（Max Heap）: 優先度が最大の要素が先に取り出される。常に「最大の値」が根（root）に位置する。これにより、最も優先度の高い（数値が大きい）要素を効率的に取り出せる。
    • ヒープを使うと、挿入と削除が O(logN) で効率的に処理できる。

heapqの使い方

Pythonには標準ライブラリとしてheapqが用意されています。heapqは最小ヒープ（Min Heap）として機能するため、挿入される値のうち最小値が常に先頭（root）に位置づけられます。

import heapq

をインポートしておけば、以下の関数が利用できます。

heapq.heapify

heapifyは、既存のリストをヒープに変換する関数です。リストを渡すと、最小ヒープに変換されます。

import heapq

data = [5, 1, 9, 2, 7]
heapq.heapify(data)
print(data)

# 例: [1, 2, 9, 5, 7] のように、要素はヒープ構造を反映した並びになる

heapifyはリストの要素数をnとしたときにO(n)の時間で処理します。

heapq.heappop、heapq.heappush

  • heapq.heappush(heap, item): ヒープheapに新たな要素itemを追加します。
  • heapq.heappop(heap): ヒープheapから最小値（root）を取り除き、その値を返します。
import heapq

heap = []
heapq.heappush(heap, 4)  # heap: [4]
heapq.heappush(heap, 1)  # heap: [1, 4]
heapq.heappush(heap, 7)  # heap: [1, 4, 7]
heapq.heappush(heap, 3)  # heap: [1, 3, 7, 4]

print(heap)  # 例: [1, 3, 7, 4]

# 最小値を取り出す
min_value = heapq.heappop(heap)
print(min_value)  # 1
print(heap)       # 例: [3, 4, 7]

heappushとheappopは、それぞれ O(logN) の時間で動作します。

heapq.nlargest、heapq.nsmallest

  • heapq.nlargest(n, iterable): iterableから 最大値上位 n 個をリストで返す
  • heapq.nsmallest(n, iterable): iterableから 最小値上位 n 個をリストで返す
import heapq

data = [5, 1, 9, 2, 7, 3, 10]

# 最大値上位3つ
top3 = heapq.nlargest(3, data)
print(top3)  # [10, 9, 7]

# 最小値上位3つ
bottom3 = heapq.nsmallest(3, data)
print(bottom3)  # [1, 2, 3]

これらの関数は、リストを新たにヒープ化するなど、内部で効率的に処理を行ってくれます。要素が多い場合も、必要な数（n）だけの値を取り出すので、全体をソートするよりも効率的な場合があります。

注意点

  • デフォルトは最小ヒープ heapqモジュールは最小ヒープのみをサポートしています。そのため、最大ヒープを実現したいときは、要素を負の値に変換してからヒープに格納するテクニックを使うのが一般的です。 
# 最大ヒープの例
import heapq

max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -10)

# 最も大きい値を取り出すには、heappopした結果を負に戻す
max_val = -heapq.heappop(max_heap)
print(max_val)  # 10
  • 要素の削除・更新が少し面倒 ヒープの中の任意の要素を直接削除したり、優先度を更新したりする操作はサポートされていません（標準ライブラリのheapqにはそういったAPIがない）。 もし任意の要素に対して頻繁に削除・更新が必要であれば、priority queueとしては queue.PriorityQueueを使う、もしくは 他のデータ構造を検討する必要があります。
  • heapqはあくまで「最小値」を素早く取り出す構造 アクセスを効率化するための構造ではありません。任意のインデックスへのアクセスにはリストと同様、O(1)で要素を得られますが、その要素がヒープ内でどの位置にあるかはあまり意味がありません（昇順にソートされているわけではない）。

    優先度付きキューの利用例

    たとえば、優先度が 小さいほど先に処理したい タスクを管理する場合は、次のように (優先度, タスク) というタプルを用いて heappush します。

    import heapq

# 優先度付きキュー（最小ヒープ）
task_queue = []

# タスクを (優先度, タスク名) の形で追加
heapq.heappush(task_queue, (3, "Task C"))
heapq.heappush(task_queue, (1, "Task A"))
heapq.heappush(task_queue, (2, "Task B"))

# 優先度の小さいタスクから順番に取り出し
while task_queue:
    priority, task_name = heapq.heappop(task_queue)
    print(f"Processing {task_name} with priority {priority}")

    実行結果（例）

    Processing Task A with priority 1
Processing Task B with priority 2
Processing Task C with priority 3
    • 最小ヒープの特性により、常に「優先度が最も小さい（数値が小さい）」要素が先に取り出されます。
    • 挿入(heappush)と削除(heappop)は、ともにO(logN)で処理されるため、多数のタスクを扱うときでも効率的です。
    • 最大優先度が先に取り出される形にしたい場合は、優先度を負の値として格納するテクニックがよく使われます。

    まとめ

    Pythonのheapqは、最小ヒープとしての挙動をシンプルに利用できる便利なモジュールです。

    • 既存のリストをヒープにするheapify
    • 値の追加・削除を行うheappush / heappop
    • 上位n個（最大/最小）を取り出すnlargest / nsmallest

    などの関数を使えば、優先度付きキューとして簡単に実装が行えます。

    タイトルとURLをコピーしました