\section{\module{heapq} ---
         ヒープキューアルゴリズム}

\declaremodule{standard}{heapq}
\modulesynopsis{ヒープキュー (別名優先度キュー) アルゴリズム。}
\moduleauthor{Kevin O'Connor}{}
\sectionauthor{Guido van Rossum}{guido@python.org}
% Theoretical explanation:
\sectionauthor{Fran\c cois Pinard}{}
\versionadded{2.3}


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

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

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

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

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

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

\begin{funcdesc}{heappush}{heap, item}
\var{item} を \var{heap} に push します。ヒープを不変に保ちます。
\end{funcdesc}

\begin{funcdesc}{heappop}{heap}
pop を行い、\var{heap} から最初の要素を返します。ヒープは不変に
保たれます。ヒープが空の場合、\exception{IndexError} が送出されます。
\end{funcdesc}

\begin{funcdesc}{heapify}{x}
リスト \var{x} をインプレース処理し、線形時間でヒープに変換します。
\end{funcdesc}

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

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

\begin{verbatim}
>>> 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
>>>
\end{verbatim}


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

\begin{funcdesc}{nlargest}{n, iterable\optional{, key}}
\var{iterable}で定義されるデータセットのうち、最大値から降順に\var{n}
個の値のリストを返します。
(あたえられた場合)\var{key}は、引数を一つとる、\var{iterable}のそれぞ
れの要素から比較キーを生成する関数を指定します: \samp{\var{key}=\function{str.lower}}
以下のコードと同等です: \code{sorted(iterable, key=key, reverse=True)[:n]} 
\versionadded{2.4}
\versionchanged[省略可能な \var{key} 引数を追加]{2.5}
\end{funcdesc}

\begin{funcdesc}{nsmallest}{n, iterable\optional{, key}}
\var{iterable}で定義されるデータセットのうち、最小値から昇順に\var{n}
個の値のリストを返します。
(あたえられた場合)\var{key}は、引数を一つとる、\var{iterable}のそれぞ
れの要素から比較キーを生成する関数を指定します: \samp{\var{key}=\function{str.lower}}
以下のコードと同等です: \code{sorted(iterable, key=key)[:n]} 
\versionadded{2.4}              
\versionchanged[省略可能な \var{key} 引数を追加]{2.5}
\end{funcdesc}

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


\subsection{理論}

(説明は Fran\c cois Pinard によるものです。このモジュールの Python コード
は Kevin O'Connor の貢献によるものです。)

ヒープとは、全ての \var{k} について、要素を 0 から数えたときに、
\code{a[\var{k}] <= a[2*\var{k}+1]} かつ 
\code{a[\var{k}] <= a[2*\var{k}+2]} となる配列です。
比較のために、存在しない要素を無限大と考えます。
ヒープの興味深い属性は \code{\var{heap}[0]} が常に最小の要素に
なることです。

上記の奇妙な不変式は、勝ち抜き戦判定の際に効率的なメモリ表現を行う
ためのものです。
以下の番号は \code{a[\var{k}]} ではなく \var{k} とします:

\begin{verbatim}
                                   0

                  1                                 2

          3               4                5               6

      7       8       9       10      11      12      13      14

    15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30
\end{verbatim}

上の木構造では、各セル \var{k} は \code{2*\var{k}+1} および
\code{2*\var{k}+2} を最大値としています。
スポーツに見られるような通常の 2 つ組勝ち抜き戦では、各セルはその
下にある二つのセルに対する勝者となっていて、個々のセルの勝者を
追跡していくことにより、そのセルに対する全ての相手を見ることが
できます。しかしながら、このような勝ち抜き戦を使う計算機
アプリケーションの多くでは、勝歴を追跡する必要はりません。
メモリ効率をより高めるために、勝者が上位に進級した際、
下のレベルから持ってきて置き換えることにすると、あるセルと
その下位にある二つのセルは異なる三つの要素を含み、かつ
上位のセルは二つの下位のセルに対して "勝者と" なります。

このヒープ不変式が常に守られれば、インデクス 0 は明らかに
最勝者となります。最勝者の要素を除去し、"次の" 勝者を見つける
ための最も単純なアルゴリズム的手法は、ある敗者要素 (ここでは上図の
セル 30 とします) を 0 の場所に持っていき、この新しい 0 を
濾過するようにしてツリーを下らせて値を交換してゆきます。不変関係が
再構築されるまでこれを続けます。この操作は明らかに、ツリー内の
全ての要素数に対して対数的な計算量となります。全ての要素について
繰り返すと、 O(n log n) のソート(並べ替え)になります。

このソートの良い点は、新たに挿入する要素が、その最に取り出す 0 番目の
要素よりも "良い値" でない限り、ソートを行っている最中に新たな要素を
効率的に追加できるというところです。

この性質は、シミュレーション的な状況で、ツリーで全ての入力
イベントを保持し、"勝者となる状況" を最小のスケジュール時刻にする
ような場合に特に便利です。あるイベントが他のイベント群の実行を
スケジュールする際、それらは未来にスケジュールされることになるので、
それらのイベント群を容易にヒープに積むことができます。
すなわち、ヒープはスケジューラを実装する上で良いデータ構造で
あるといえます (私は MIDI シーケンサで使っているものです :-).

これまでスケジューラを実装するための様々なデータ構造が広範に
研究されています。ヒープは十分高速で、速度もおおむね一定であり、
最悪の場合でも平均的な速度とさほど変わらないため良いデータ構造と
いえます。しかし、最悪の場合がひどい速度になることを除き、
たいていでより効率の高い他のデータ構造表現も存在します。

ヒープはまた、巨大なディスクのソートでも非常に有用です。
おそらくご存知のように、巨大なソートを行うと、複数の "ラン (run)" 
(予めソートされた配列で、そのサイズは通常 CPU メモリの量に関係
しています) が生成され、続いて統合処理 (merging) がこれらのランを
判定します。この統合処理はしばしば非常に巧妙に組織されています
\footnote{現在使われているディスクバランス化アルゴリズムは、最近は
もはや巧妙というよりも目障りであり、このためにディスクに対するシーク
機能が重要になっています。巨大な容量を持つテープのようにシーク不能な
デバイスでは、事情は全く異なり、個々のテープ上の移動が可能な限り
効率的に行われるように非常に巧妙な処理を (相当前もって) 行わねば
なりません (すなわち、もっとも統合処理の "進行" に関係があります)。
テープによっては逆方向に読むことさえでき、巻き戻しに時間を取られる
のを避けるために使うこともできます。正直、本当に良いテープソート
は見ていて素晴らしく驚異的なものです！ソートというのは常に偉大な
芸術なのです！:-)}。
重要なのは、最初のソートが可能な限り長いランを生成することです。
勝ち抜き戦はこれを行うための良い方法です。もし利用可能な全ての
メモリを使って勝ち抜き戦を行い、要素を置換および濾過処理して
現在のランに収めれば、ランダムな入力に対してメモリの二倍の
サイズのランを生成することになり、大体順序づけがなされている入力に
対してはもっと高い効率になります。

さらに、ディスク上の 0 番目の要素を出力して、現在の勝ち抜き戦に
(最後に出力した値に "勝って" しまうために) 収められない入力を得た
なら、ヒープには収まらないため、ヒープのサイズは減少します。
解放されたメモリは二つ目のヒープを段階的に構築するために巧妙に再利用
することができ、この二つ目のヒープは最初のヒープが崩壊していく
のと同じ速度で成長します。最初のヒープが完全に消滅したら、
ヒープを切り替えて新たなランを開始します。なんと巧妙で
効率的なのでしょう！

一言で言うと、ヒープは知って得するメモリ構造です。
私はいくつかのアプリケーションでヒープを使っていて、
`ヒープ' モジュールを常備するのはいい事だと考えています。 :-)

