5.12 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)
itemheap に push します。ヒープを不変に保ちます。

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

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

heapreplace( heap, item)
heap から最小の要素を pop して返し、新たに item を push します。ヒープのサイズは変更されません。 ヒープが空の場合、 IndexError が送出されます。 この関数は heappop() に次いで heappush() を送出するよりも効率的で、固定サイズのヒープを用いている場合には より適しています。返される値は item よりも大きくなるかも しれないので気をつけてください! これにより、このルーチンの合理的な 利用法は条件つき置換の一部として使われることに制限されています。
        if item > heap[0]:
            item = heapreplace(heap, 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
>>>

このモジュールではさらに2つのヒープに基く汎用関数を提供します。

nlargest( n, iterable)
iterableで定義されるデータセットのうち、最大値から降順にn 個の値のリストを返します。 以下のコードと同等です: sorted(iterable, reverse=True)[:n] バージョン 2.4 で 新たに追加 された仕様です。

nsmallest( n, iterable)
iterableで定義されるデータセットのうち、最小値から昇順にn 個の値のリストを返します。 以下のコードと同等です: sorted(iterable)[:n] バージョン 2.4 で 新たに追加 された仕様です。

どちらの関数もnの値が小さな場合に最適な動作をします。 大きな値の時にはsorted()関数の方が効率的です。 さらに、n==1の時にはmin()およびmax() 関数 の方が効率的です。



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