メインコンテンツまでスキップ

優先度付きキュー

優先度付きキューとは

要素を取り出す際に入れた順ではなく、何らかの取り出し順(優先度)を定めて取り出していくデータ構造のことを優先度付きキューという。

イメージ図

優先度付きキューは様々なデータ構造(木構造・配列)を用いて実装することが可能である。

ヒープ

優先度付きキューの実装の 1 つで子要素は親要素より常に大きい(小さい)か等しいという制約を持つ 2 分木構造の事をヒープという。

イメージ図

図のように子は必ず自分より大きいか小さくなっている。

コード

heap.py
import heapq

box = [3, 19, 7, 16, 18, 2, 11, 4, 5]

# ヒープの並びに変換 → 2 4 3 5 18 7 11 16 19
heapq.heapify(box)

# 要素の取り出し → 2
b = heapq.heappop(box)

# 要素を追加 → 3 4 7 5 18 19 11 16 10
heapq.heappush(box, 10)

# 要素を追加 → 1 3 7 5 4 19 11 16 10 18
heapq.heappush(box, 1)
備考

Python だと小さい順に並び、大きい順に並べることができない。そのため、全ての値に-1 を掛けること、つまり大小を反転させることで大きい順から値を取り出すことができる。