【Python】優先度付きキュー（Priority Queue）とは？

初めに

まず、優先度付きキュー（Priority Queue）は、各要素に優先度を持たせ、優先度の高い要素を先に取り出すデータ構造です。通常のキュー（FIFO: 先入れ先出し）とは異なり、優先度が高い順に要素を取り出すという特徴があります。

仕組み

優先度付きキューでは、各要素が「値」と「優先度」を持ち、優先度の高いものから処理されるようになっています。

主要な操作

1. 要素の追加
   • 値と優先度を指定してキューに追加する。
2. 要素の取り出し
   • 最も高い優先度を持つ要素を取得し、キューから削除する。
3. 優先度の変更
   • すでにキューにある要素の優先度を変更する。

メリット

• 最小値・最大値を素早く取り出せる
• 挿入順は気にしなくても良い

デメリット

• 特定の要素の検索・更新が遅い
• データの並び順が保証されない
• 大量のデータを頻繁に挿入・削除する場合は、オーバーヘッドが発生する

実装例(heapqモジュールを使う)

基本的な構文

import heapq

# 空の優先度付きキューを作成
pq = []

# 要素を追加（優先度, 値）のタプルで追加する
heapq.heappush(pq, (2, "task-2"))  # 優先度2
heapq.heappush(pq, (1, "task-1"))  # 優先度1（最優先）
heapq.heappush(pq, (3, "task-3"))  # 優先度3

# 優先度の低い（数値が小さい）ものから取り出される
print(heapq.heappop(pq))  
print(heapq.heappop(pq))  
print(heapq.heappop(pq)) 

出力結果
(1, 'task-1')
(2, 'task-2')
(3, 'task-3')

ポイント

• heapq.heappush(pq, (優先度, 値)) で要素を追加
• heapq.heappop(pq) で要素を取り出す
• heapq はデフォルトで最小ヒープ（小さい値が優先される）として機能する

最大優先度付きキュー

デフォルトでは最小値が優先されるため、最大値を優先したい場合は優先度の符号を反転します。

import heapq

pq = []
heapq.heappush(pq, (-2, "task-2"))  # -2 
heapq.heappush(pq, (-1, "task-1"))  # -1
heapq.heappush(pq, (-3, "task-3"))  # -3

# 取り出し（元の符号を戻す）
print((-pq[0][0], heapq.heappop(pq)[1]))  
print((-pq[0][0], heapq.heappop(pq)[1])) 
print((-pq[0][0], heapq.heappop(pq)[1]))  

出力結果
(3, 'task-3')
(2, 'task-2')
(1, 'task-1')

ポイント

• 優先度に - をつけて登録し、取り出すときに元の符号に戻すことで最大優先度キューを実現できる