Python

[python] pythonの優先度付きキュー/ヒープキュー(Priority Queue/Heap Queue)

本記事を読む前に、
pythonのキューという記事読んでおくのをお勧めします。

優先度付きキューとは

優先順位付きキュー(priority queue)は、 ヒープキューとしても知られています。
言い換えれば、優先度付きキューは ヒープ(heap)を使って実装するのがほとんどです。
そのエントリは ソートされ、 最も低い値のエントリが最初に取り出されます。

データ構造を図で表現しますと、下記のようにな ツリー構造 になります。

Kobito.P6LLHa.png

heapq と queue.PriorityQueue

pythonでは、 heapqqueue.PriorityQueue 2種類の優先度付きキューがあります。

queue.PriorityQueue は、heapqモジュールを利用して実装されたスレッドセーフ(マルチスレッド対応)の優先順位付きキューとなります。

要は、

  • シングルスレッドの場合は heapqを使用(スレッドセーフでない分スピードが早いため)。
  • マルチスレッドの場合は queue.PriorityQueue を使用(heapqを使えない)。

スピード関連の比較結果は こちらのサイトにまとめてあります。

コメントを残す