二分ヒープとしての木 — ヒープ性質の可視化

二分ヒープとしての木

二分ヒープはヒープ性質を満たす完全二分木です：最大ヒープではすべての親がその子以上、最小ヒープではすべての親がその子以下です。

最大ヒープの例

木のビュー:             配列: [90, 70, 80, 30, 50, 60, 40]
       90
      /  \
    70    80
   / \   / \
  30 50 60 40

i の親: floor((i-1)/2)
i の左の子: 2i + 1
i の右の子: 2i + 2

ヒープ操作

挿入（バブルアップ / シフトアップ）:

1. 末尾に新しい要素を追加
2. 親と比較。ヒープ性質に違反する場合、親と交換
3. 性質が復元されるかルートに到達するまで繰り返す
4. 時間: O(log n)

最大/最小の取り出し（バブルダウン / シフトダウン）:

1. ルート（最大または最小の要素）を削除
2. 最後の要素をルート位置に移動
3. 子と比較。大きい（最大ヒープ）または小さい（最小ヒープ）子と交換
4. 性質が復元されるまで繰り返す
5. 時間: O(log n)

ヒープ構築（Heapify）:

1. 最後の非リーフノード（インデックス n/2 - 1）から開始
2. 各ノードをシフトダウン
3. 時間: O(n)

ヒープ vs BST

性質	ヒープ	BST
順序付け	親と子の間のみ	左 < 親 < 右
構造	完全二分木	任意の形状
最小/最大の検索	O(1)	O(h)
探索	O(n)	O(h)
挿入	O(log n)	O(h)