形と大小関係の二つを守る
最小二分ヒープでは、木の形と値の順序を別々に定めます。形は、最下段以外が埋まり、最下段も左から詰めた完全二分木です。値は、どの親もその子以下になるように置きます。親子を根までたどれば、根がすべての値以下であることが分かります。一方、兄弟同士の大小や、左部分木と右部分木の全体の順序は決まりません。配列[1,5,2,9,7,4]は有効な最小ヒープですが昇順ではありません。「最小がすぐ見える」と「すべてが並んでいる」を区別してください。二分探索木の左と右の範囲条件を、この構造へ持ち込んでも正しい探索はできません。
完全二分木を配列に対応させる
配列の添字を0から数えると、添字iの左の子は2i+1、右の子は2i+2です。根以外の親は(i−1)を2で割った整数部分で求められます。子の添字が配列長以上なら、その子は存在しません。完全二分木の形を保つことで、ポインタを各ノードへ持たせず、配列の添字から関係を復元できます。ただし、この計算が示すのは木の配置です。キーの値から目的の添字を直接得られるわけではありません。実装では、空の配列から最小値を読む操作、根の親を計算する操作、最後のノードの存在しない子へ進む操作を防ぐ境界条件が必要になります。
末尾へ置いてから上へ動かす
[2,5,4,9,7]に1を追加します。最初は末尾へ置いて[2,5,4,9,7,1]とし、完全二分木の形を保ちます。新しい要素の親は添字2の4なので、1と4を交換します。次に親である根の2と交換すると[1,5,2,9,7,4]になり、親子条件が回復します。他の枝は変更していないため、修復するのは追加位置から根への一本の経路だけです。木の高さは要素数の対数程度なので、この上への移動は最悪O(log n)です。ただし動的配列の再確保が必要な一回には、配列自体の移動費用も加わります。ヒープの比較・交換と、保存領域の拡張を区別した評価が必要です。
import heapq
h = [2, 5, 4, 9, 7]
heapq.heappush(h, 1)
assert h == [1, 5, 2, 9, 7, 4]
assert heapq.heappop(h) == 1
assert h == [2, 5, 4, 9, 7]
assert all(h[(i - 1) // 2] <= h[i] for i in range(1, len(h)))
取り出した根を末尾の値で埋める
[1,5,2,9,7,4]から最小値1を取り出すには、最後の4を根へ移し、配列を一つ短くして[4,5,2,9,7]とします。根の子5と2のうち小さい2と交換すれば、結果は[2,5,4,9,7]です。小さくない方の子を選ぶと、もう一方の子より親が大きいままになる場合があります。毎回両方の子を比較し、必要なら小さい方へ下げるのが基本です。末尾を使うのは形を保つためで、値が最小に近いからではありません。最小値を見るだけなら根を返してO(1)、削除して条件を直すなら最悪O(log n)と、問い合わせと更新を分けて考えます。
配列全体の構築はなぜO(n)か
n個の値を一つずつ挿入すれば、単純な上界はO(n log n)です。一方、既存配列をヒープにするなら、葉に子はないので修復不要です。最後の親から根へ向かって、各部分木を下向きに修復できます。高い位置の修復は長くても、そのようなノードは少なく、葉に近い多数のノードはほとんど動きません。葉から測った高さがhのノード数は、おおむねn/(2^h)以下です。そのため、仕事はn×Σ(h/2^h)という形で抑えられます。この級数が定数へ収まることから、全体はO(n)です。全ノードが根と同じ高さ分だけ動くとして足すと、必要以上に緩い評価になります。
優先度の変更と同順位を扱う
最小値を繰り返し選ぶ用途では便利でも、基本形のヒープは任意のキーの場所をすぐには見つけられません。特定の要素の優先度を変えたいなら、要素IDから添字への対応表を保ち、交換のたびに表も更新する方法があります。別の方法として、新しい候補を追加し、取り出した際に古い候補か確認して捨てる設計もあります。この方法では古い候補の領域が残るので、メモリ上限と掃除の条件も必要です。同じ優先度を入力順に処理したければ、比較キーを優先度と連番の組にします。連番は数値の同順位を解くものであり、優先度が異なる処理まで先着順にするものではありません。
小さな例と性質の両方で検証する
挿入と取り出しの例だけでなく、すべての子について、親の値がその子以下であることを検査すると、修復の方向や境界の誤りを見つけやすくなります。さらに、入力した値をすべて取り出した列が昇順になり、個数と重複が保たれることを確認します。空、一要素、すべて同じ値、既に整列済み、逆順なども試してください。浮動小数点のNaNのように通常の全順序を満たさない値を受け入れる場合は、比較の契約を別に決める必要があります。ヒープ条件が正しいことと、複数スレッドから安全に更新できることは別です。並行アクセスには、使う実装やロックなどの明示的な同期規則が必要になります。