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): item を heap に 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() 関数の方が効率的です。

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

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

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