5.10 `heapq` -- ヒープキューアルゴリズム

バージョン2.3 以降で新規追加された仕様です。

このモジュールではヒープキューアルゴリズムの一実装を提供しています。優先度キューアルゴリズムとしても知られています。

ヒープとは、全ての k に対して、ゼロから要素を数えていった際に、 heap[k] <= heap[2*k+1] かつ heap[k] <= heap[2*k+2] となる配列です。比較のために、存在しない要素は無限大として扱われます。ヒープの興味深い属性は heap[0] が常に最小の要素になることです。

以下の API は教科書におけるヒープアルゴリズムとは 2 つの側面で異なっています: (a) ゼロベースのインデクス化を行っています。これにより、ノードに対するインデクスとその子ノードのインデクスの関係がやや明瞭でなくなりますが、Python はゼロベースのインデクス化を使っているのでよりしっくりきます。(b) われわれの pop メソッドは最大の要素ではなく最小の要素 (教科書では "min heap:最小ヒープ" と呼ばれています; 教科書では並べ替えをインプレースで行うのに適した "max heap:最大ヒープ" が一般的です)。

これらの 2 点によって、ユーザに戸惑いを与えることなく、ヒープを通常の Python リストとして見ることができます: heap[0] が最小の要素となり、 heap.sort() はヒープを不変なままに保ちます!

ヒープを作成するには、[] に初期化されたリストを使うか、 heapify() を用いて要素の入ったリストを変換します。

以下の関数が提供されています:

heappush( heap, item): item を heap に push します。ヒープを不変に保ちます。

heappop( heap): pop を行い、heap から最初の要素を返します。ヒープは不変に保たれます。ヒープが空の場合、IndexError が送出されます。

heapify( x): リスト x をインプレース処理し、線形時間でヒープに変換します。

heapreplace( heap, item): heap から最小の要素を pop して返し、新たに item を push します。ヒープのサイズは変更されません。ヒープが空の場合、 IndexError が送出されます。この関数は heappop() に次いで heappush() を送出するよりも効率的で、固定サイズのヒープを用いている場合にはより適しています。返される値は item よりも大きくなるかもしれないので気をつけてください! これにより、このルーチンの合理的な利用法が制限されています。

使用例を以下に示します:

>>> from heapq import heappush, heappop
>>> heap = []
>>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
>>> for item in data:
...     heappush(heap, item)
...
>>> sorted = []
>>> while heap:
...     sorted.append(heappop(heap))
...
>>> print sorted
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> data.sort()
>>> print data == sorted
True
>>>

ご意見やご指摘をお寄せになりたい方は、 このドキュメントについて... をご覧ください。

5.10 heapq -- ヒープキューアルゴリズム

5.10 `heapq` -- ヒープキューアルゴリズム