Pythonの優先度付きキュー（Priority Queue）入門ガイド：queue.PriorityQueueとheapqの使い方

Pythonの優先度付きキューとは？

Pythonの優先度付きキュー（Priority Queue）は、データを特定の順序で管理するためのデータ構造です。要素ごとに「優先度」が設定され、優先度の高いものから順に取り出せます。Pythonで優先度付きキューを実装する方法は主に2つあり、標準ライブラリのqueue.PriorityQueueクラスを使う方法と、heapqモジュールを使う方法があります。

たとえば、リスト内の各アイテムの値に基づいてデータを並べたいケースを考えてみましょう。「最も値の大きい項目を先頭に表示し、最小の値は最後に表示したい」といった場面です。

こうしたニーズに応えてくれるのが優先度付きキューです。優先度付きキューは、キーの値に基づいてデータを昇順に格納するデータ構造であり、キュー内の最小値・最大値へ簡単にアクセスできます。

本記事では、まずリストで優先度付きキューを作るべきではない理由を解説し、そのうえで、より効率的な2つの実装方法をコード例とともに紹介します。

Pythonにおける優先度付きキューの基本

優先度付きキューとは、通常のキューを拡張したデータ構造で、「どの要素が最も高い優先度を持つか」という順序でデータを格納します。各要素の優先度は、その要素の値によって決まります。

コンピュータサイエンスにおいて、キューは「先入れ先出し（FIFO: First-In, First-Out）」の順序でアイテムを管理するデータ構造です。この仕組みが役立つ場面は数多くあります。

たとえば、レストラン向けの注文管理アプリを作っているとしましょう。最初に注文したお客様が、後から注文したお客様よりも先に対応されるべきです。このような注文の追跡には、まさにキューが適しています。

Pythonで優先度付きキューを定義する方法は、次の2つです。

• queue.PriorityQueueクラスを使う方法
• heapqモジュールを使う方法

リスト構造でも優先度付きキューを定義することは可能ですが、この方法はPriorityQueueクラスやheapqモジュールを使う場合に比べて効率が劣ります。

queue.PriorityQueueで優先度付きキューを作る

queue.PriorityQueueクラスは、Pythonで優先度付きキューを作成するためのクラスです。Pythonのqueueライブラリに含まれているため、利用するには事前にインポートが必要です。キューからアイテムを取り出すには、get()メソッドを使用します。

まず、次のimport文でPriorityQueueクラスをコードに取り込みます。

from queue import PriorityQueue

それでは、地元のコンサートのチケット保有者向けに優先度付きキューを作成する例を見てみましょう。

from queue import PriorityQueue

ticket_holders = PriorityQueue()

ticket_holders.put((3, 'Paul'))
ticket_holders.put((1, 'Miles'))
ticket_holders.put((2, 'Dani'))

while not ticket_holders.empty():
    item = ticket_holders.get()
    print(item)

このコードを実行すると、次の出力が得られます。

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

コードの流れを解説します。まずqueueライブラリからPriorityQueueクラスをインポートし、ticket_holdersという名前の優先度付きキューを初期化しています。続いて、チケット番号と名前をペアにしたタプルを3つ、キューに挿入しました。

最後にwhileループでticket_holdersキューの各アイテムを順に処理し、get()メソッドでアイテムを取り出して表示しています。出力結果を見ると、チケット番号の小さい順（＝優先度の高い順）にアイテムが取り出されていることがわかります。

queue.PriorityQueueは効率的で扱いやすいため、優先度付きキューが必要な場面での第一候補となる選択肢です。

heapqモジュールで優先度付きキューを作る

heapqモジュールを使っても、Pythonの優先度付きキューを定義できます。heapqによるデータ構造（ヒープ）では、アイテムが優先度の順に取り出されます。ヒープでは最小の値が最も高い優先度を持ち、値が大きいほど優先度は低くなります（ミニヒープ方式）。

heapqモジュールを使う前に、次のimport文でコードに取り込む必要があります。

import heapq

先ほどの例と同じく、コンサートのチケット保有者情報を格納する優先度付きキューを、heapqモジュールで作ってみましょう。

import heapq

ticket_holders = []

heapq.heappush(ticket_holders, (3, 'Paul'))
heapq.heappush(ticket_holders, (1, 'Miles'))
heapq.heappush(ticket_holders, (2, 'Dani'))

while ticket_holders:
    item = heapq.heappop(ticket_holders)
    print(item)

実行結果は以下のとおりです。

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

まずheapqライブラリをインポートし、ticket_holdersという空のリストを初期化します。次にheappush()メソッドを使って、チケット番号と名前を含むタプルを3つヒープに追加しました。

その後、whileループでキュー内の各アイテムを処理します。ループ内ではheappop()メソッドでキューの先頭からアイテムを取り除き、取り除いたアイテムをコンソールに出力しています。実行結果を見ると、すべてのアイテムが優先度の順に表示されていることが確認できます。

リストを優先度付きキューとして使うべきでない理由

技術的には、Pythonのリストを使って優先度付きキューを作ることも可能です。リストを作成し、昇順に並べ替えればよいだけです。

しかし、これはあまり効率的な方法ではありません。リスト内のアイテムが変化するたびに、リスト全体を再び並べ替える必要があり、その分時間がかかってしまうのです。

保存する値が少数であれば、従来のリストを優先度付きキューとして使っても問題ありません。しかし、規模の大きなキューを作りたい場合、リストは適した選択肢とは言えません。

参考までに、リストを使った優先度付きキューの例を見てみましょう。コンサートに最初に入場すべきチケット保有者の順序を格納するキューを作るとします。

ticket_holders = []

ticket_holders.append((3, 'Paul'))
ticket_holders.append((1, 'Miles'))
ticket_holders.append((2, 'Dani'))

ticket_holders.sort(reverse=True)

while ticket_holders:
    item = ticket_holders.pop()
    print(item)

実行結果：

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

ここではticket_holdersというリストを作成し、チケット番号と名前を含むタプルを3つ追加しました。その後、Pythonのsort()関数を使ってリストを逆順に並べ替えています。

そしてwhileループでticket_holdersリストの各アイテムを反復処理し、リスト末尾のアイテムをpop()で取り出してはコンソールに出力しています。これにより、優先度の順にアイテムが表示される仕組みです。

まとめ

Pythonで優先度付きキューを作成する最も一般的な方法は、heapqモジュールを使うか、queue.PriorityQueueクラスを使うかの2つです。技術的にはリストを優先度付きキューとして使うこともできますが、このアプローチはデータ量が増えたときにスケールしません。

本記事では、具体例を挙げながらPythonで優先度付きキューを作成する方法を解説しました。これで、プロのように自分自身の優先度付きキューを作成するための基礎知識は身についたはずです。さらに学習を深めたい方は、Python公式ドキュメントのqueueおよびheapqのページもあわせて参照してみてください。