優先度付きキュー

優先度付きキュー（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

`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（最小値）

最大ヒープ¶

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

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

(優先度, 値) のタプルを 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}')

`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}')

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

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

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')