優先度付きキュー

優先度付きキュー#

優先度付きキュー（Priority Queue） は各要素に優先度を持たせ、優先度の高いものから順に取り出せるデータ構造。

通常は ヒープ（Heap） を使って実装される。

操作：

push(x): 要素 x を追加する（\(O(\log n)\)）
pop(): 最も優先度の高い要素を取り出す（\(O(\log n)\)）
peek(): 最も優先度の高い要素を参照する（\(O(1)\)）

計算量#

ヒープ（二分ヒープ）による実装での各操作の計算量：

操作	計算量	説明
`push`	\(O(\log n)\)	末尾に追加後、ヒープ条件を満たすまで親と交換（sift-up）
`pop`	\(O(\log n)\)	根を取り出し末尾の要素を根に移動後、再構築（sift-down）
`peek`	\(O(1)\)	根（先頭要素）を参照するだけ
`heapify`	\(O(n)\)	既存のリストをヒープに変換

他のデータ構造との比較（\(n\) 要素、最小値の取得と削除を繰り返す場合）：

データ構造	push	pop（最小値）	peek（最小値）
ヒープ	\(O(\log n)\)	\(O(\log n)\)	\(O(1)\)
ソート済み配列	\(O(n)\)	\(O(1)\)	\(O(1)\)
未ソート配列	\(O(1)\)	\(O(n)\)	\(O(n)\)

優先度付きキューは push と pop を繰り返す用途に最適なバランスを持つ。

`heapq` モジュール#

Python の heapq は 最小ヒープ（min-heap） として動作する。最小値が常に先頭に来る。

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 3

1
2
3

`heapify` — \(O(n)\) でリストをヒープ化#

リストを一から push で構築すると \(O(n \log n)\) かかるが、heapify は \(O(n)\) で変換できる。

import heapq

data = [5, 3, 8, 1, 4]
heapq.heapify(data)  # in-place で O(n)
print(data)          # ヒープ条件を満たすリスト

print(heapq.heappop(data))  # 1（最小値）

[1, 3, 8, 5, 4]
1

最大ヒープ#

heapq は最小ヒープのみサポートするため、最大ヒープとして使うには値を負にする。

import heapq

heap = []
for x in [3, 1, 2]:
    heapq.heappush(heap, -x)  # 符号を反転して push

print(-heapq.heappop(heap))  # 3
print(-heapq.heappop(heap))  # 2
print(-heapq.heappop(heap))  # 1

3
2
1

タプルによる優先度の指定#

(優先度, 値) のタプルを push することで、任意の優先度を指定できる。

import heapq

heap = []
heapq.heappush(heap, (2, 'task B'))
heapq.heappush(heap, (1, 'task A'))  # 優先度高
heapq.heappush(heap, (3, 'task C'))

while heap:
    priority, task = heapq.heappop(heap)
    print(f'priority={priority}: {task}')

priority=1: task A
priority=2: task B
priority=3: task C

`queue.PriorityQueue`#

スレッドセーフな優先度付きキューが必要な場合は queue.PriorityQueue を使う。

from queue import PriorityQueue

pq = PriorityQueue()
pq.put((2, 'task B'))
pq.put((1, 'task A'))
pq.put((3, 'task C'))

while not pq.empty():
    priority, task = pq.get()
    print(f'priority={priority}: {task}')

priority=1: task A
priority=2: task B
priority=3: task C

活用例：ダイクストラ法#

優先度付きキューは最短経路アルゴリズム（ダイクストラ法）で頻繁に使われる。コストの小さいノードから順に探索することで効率よく最短距離を求められる。

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]  # (コスト, ノード)

    while heap:
        cost, u = heapq.heappop(heap)
        if cost > dist[u]:
            continue
        for v, weight in graph[u]:
            new_cost = cost + weight
            if new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(heap, (new_cost, v))

    return dist

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': [],
}

dijkstra(graph, 'A')

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

優先度付きキュー

Contents