ヒープ

二分ヒープは完全二分木で、親が子より低い優先度にならないようにします。最小ヒープなら親値は子以下、最大ヒープなら逆です。極値が根にあるため peek は O(1)、挿入と extract_top のヒープ調整は O(log n)。全体を配列に置けます。

制約は上下関係だけです。部下が上司を上回れない組織図でも、同僚の横並びに順位はない、という形です。

ヒープの仕組み

添字 i の子は 2i + 1、2i + 2、親は (i − 1) // 2。完全二分木は最下段以外を満たし、最下段を左から詰めるため、配列に穴がありません。親子リンクを別に保存せず添字から復元できます。

peek は data[0] を読みます。

insert は末尾へ追加して形を保ち、上方修復します。新値が親より優先なら交換して一段上がります。添字 0 に達するか、上回れない親に出会えば停止します。最小ヒープは < で上昇を判定します。

extract_top は根を返り値として保存し、末尾を取り出して添字 0 へ置き、下方修復します。各段階で左右の子から優先度の高い方を選び、それが現在値より優先なら交換してその部分木へ進みます。子がないか、子が上回らなければ停止します。末尾で根を埋めることで完全な形を壊しません。

下方修復は左、右の順に調べ、最良候補を決めてから交換します。比較は厳密なので、左右が同値なら左が候補に残ります。

最小と最大の切り替えは比較器 < / > だけです。上の木と下の配列を同じ交換で動かします。

操作をステップで追う

既定は空の最小ヒープ、表示容量 10。5、3、8、1、9、2 を挿入し、先頭を抽出します。

1. insert(5)：添字 0 へ。i > 0 が偽で修復不要。[5]。
2. insert(3)：添字 1 へ追加し、3 < 5 で arr[1] ↔ arr[0]。[3, 5]。
3. insert(8)：添字 2、親は 0。8 ≥ 3 なので交換せず [3, 5, 8]。
4. insert(1)：添字 3 から 1 < 5 で arr[3] ↔ arr[1]、[3, 1, 8, 5]。次に 1 < 3 で arr[1] ↔ arr[0]、[1, 3, 8, 5]。二比較二交換で根へ到達。
5. insert(9)：添字 4、親 3 より大きく [1, 3, 8, 5, 9]。
6. insert(2)：添字 5 から親 8 に勝ち、arr[5] ↔ arr[2]。根 1 には勝たず停止。[1, 3, 2, 5, 9, 8]。根 1、子 3 と 2、3 の下は 5 と 9、2 の下は 8 だけ。
7. extract_top()：1 を返す。末尾の添字 5 の 8 を根へ移し、[8, 3, 2, 5, 9]。子 3 と 2 から 2 を選び、2 < 8 で arr[0] ↔ arr[2]。[2, 3, 8, 5, 9]。添字 2 の左の子は 5 で範囲外なので停止。新しい先頭は二番目に小さい 2。

画面は候補を実際の比較式付き破線で結びます。下方修復では選んだ子に色を付けてから交換し、木と配列を同期させます。挿入値は確定時に緑で示し、抽出した根は上へ離れます。

時間・空間計算量

n ノードの完全二分木は ⌈log₂(n+1)⌉ レベルで、交換ごとに一段動きます。百万要素で約二十段です。配列は親子ポインターを追加しません。ただし基底の動的配列を拡張する回は O(n) の移動が必要で、多数の挿入に含めれば償却 O(log n) です。

既存 n 要素から最後の内部ノードを起点に逆順で下方修復すると、構築は O(n)。O(n log n) ではありません。多くのノードは底に近く、移動が少ないか不要だからです。

境界ケース

• 空：peek は None、extract_top はアンダーフロー。ボタンを有効に保ち、失敗経路を見られる。
• 一要素：唯一の値を取り出した後は if self.data: が偽。末尾を根へ移す処理と下方修復はしない。
• 重複・同値：最小ヒープの規則は ≤ なので同値を許す。同値の右の子は左候補を置き換えない。
• 表示容量：4–15、既定 10 は画面の制約。超過時は表示上限と説明する。実際は利用可能な保存領域に従う。

よくある間違い

• 配列を整列済みと思う。 最後の [2, 3, 8, 5, 9] は 8 が 5 より前でも有効です。極値を繰り返し抽出すると整列順になり、ヒープソートの基礎となります。
• 下方修復で別の子を選ぶ。 最小ヒープで大きい子と交換すると、小さい子との違反が残ります。最良の子を選び、比較して交換します。
• 添字の規約を混ぜる。 0 始まりは 2i + 1、2i + 2、(i − 1) // 2。1 始まりは 2i、2i + 1、i // 2 です。
• 任意値の高速検索を期待する。 非極値の位置は決まらず、最悪 O(n)。キー検索や順序付き範囲なら平衡 BST が適します。
• 比較器を不用意に反転する。 < を > に変えると極値の向きが変わります。内部構造が有効でも、呼び出し側の期待は壊れます。