# 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
    >>>