このモジュールではヒープキューアルゴリズムの一実装を提供しています。 優先度キューアルゴリズムとしても知られています。
ヒープとは、全ての 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() を用いて要素の入ったリストを変換します。
以下の関数が提供されています:
heap, item) |
heap) |
x) |
heap, 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つのヒープに基く汎用関数を提供します。
n, iterable[, key]) |
sorted(iterable, key=key, reverse=True)[:n]
バージョン 2.4 で 新たに追加 された仕様です。
バージョン 2.5 で 変更 された仕様:
省略可能な key 引数を追加
n, iterable[, key]) |
sorted(iterable, key=key)[:n]
バージョン 2.4 で 新たに追加 された仕様です。
バージョン 2.5 で 変更 された仕様:
省略可能な key 引数を追加
どちらの関数もnの値が小さな場合に最適な動作をします。
大きな値の時にはsorted()関数の方が効率的です。
さらに、n==1
の時にはmin()およびmax() 関数
の方が効率的です。