Pythonの技法:heapqモジュールによる優先順位付きキューの実装

文:Nick Gibson(Builder AU)  翻訳校正:原井彰弘
2008-01-08 12:00:00
  • このエントリーをはてなブックマークに追加

 Pythonには、順序付きのリストでヒープを実装するheapqモジュールが用意されている。このモジュールを利用することで、アイテムの追加や削除の際もソートされた状態が維持される「優先順位付きキュー」を、素早く簡単に作成することができるのである。このheapqモジュールでは、常に最小のアイテムを返す「最小ヒープ」を実現するための関数が定義されており、以下のようにheappush関数を用いて値の追加を、heappop関数で値の削除を行える。

>>> from heapq import heappush, heappop
>>> heap = []
>>> heappush(heap, 2)
>>> heappush(heap, 10)
>>> heappush(heap, 4)
>>> heappush(heap, 5)
>>> heappop(heap)
2
>>> heappop(heap)
4
>>> heappop(heap)
5
>>> heappop(heap)
10

 また、あらかじめリストとして値がまとめられている場合は、次のようにheapqのheapify関数を用いてヒープ化できる。

>>> from heapq import heapify
>>> heap = [3,4,5,6,9,1,7,2,8]
>>> heapify(heap)
>>> heap
[1, 2, 3, 4, 9, 5, 7, 6, 8]
>>> heappop(heap)
1

 ここで注意していただきたいのは、heapify関数はリストのソートを行うわけではないということである。リストを用いて実装されたヒープは、フラット化されたツリー構造に近い。ヒープでは、リスト中の要素heap[k]はheap[k*2 + 1]とheap[k*2 + 2]よりも小さいか同じでなければならず、リストの最初のアイテムは常に最小の値となることが保証されている程度なのである。そして、最初のアイテムが削除された場合は、2つ目もしくは3つ目の要素が先頭になり、ヒープ内の他の要素はそれにあわせて調整されるのようになっている。

 ヒープに関してさらに知りたければ、Wikipediaのページを参照して欲しい。

 ところで、ヒープをこのような方法(すべてのアイテムを一度に追加し、削除もすべて一度に行う方法)で利用することは、単純にリストをソートすることと比較して何のメリットもない。優先順位付きキューの本当のメリットは、要素を追加しながら、その間に最小値の削除も行う必要がある場合に発揮されるのである。それでは、以下の例を見てみよう。

  • 新着記事
  • 特集
  • ブログ