lecture/algorithm/data-structures/木とヒープの基本-講義.n.md
木とヒープの基本
algorithmdata-structuresundergraduatelecture
導入
この講義で最重要なのは、木は「親子関係で要素を整理する構造」であり、ヒープはその上に「親と子の大小関係」を課したものだということです。
配列は横に並べる構造ですが、木は分岐しながら下へ広がります。この見方が分かると、優先度つきキューや探索木の話へ自然に進めます。
用語と定義
木 とは、根から枝分かれする階層構造です。
ヒープ とは、完全二分木の形をもち、親と子の間に大小関係をもつ構造です。
優先度つきキュー とは、最も優先度の高い要素から取り出す構造です。
方針
まず木を「親と子」で読む構造として捉えます。そのうえで、ヒープでは「親が子より大きい」または「小さい」という条件を加えると、最小値や最大値を取り出しやすくなることを見ます。
直感的な説明
教室の席順のように横に並んだ構造では、中央の近くも端も同じように 1 列の中にあります。いっぽう組織図のような構造では、「だれの下にだれがいるか」が重要です。木はこのような階層を表すのに向いています。
厳密な説明
1. 木
根を 1 つもち、各節点から子へ枝がのびる構造を考えます。循環がないことが重要です。
2. ヒープ
最大ヒープでは、どの節点でも
\text{親の値} \ge \text{子の値}
が成り立ちます。
3. 計算量
完全二分木では高さがだいたい \log n なので、ヒープでの挿入や削除は多くの場合 O(\log n) です。
見分け方
- 親子関係や階層を使って整理したいなら、木を疑います。
- 最小値や最大値を繰り返し取り出したいなら、ヒープが候補です。
- 完全に整列された順序が必要なら、ヒープだけでは足りないことに注意します。
最終形
\boxed{\text{木}=\text{階層構造}}
\boxed{\text{ヒープ}=\text{木}+\text{親子の大小関係}}
\boxed{\text{ヒープ操作の典型} = O(\log n)}
一言でいうと
- 木は階層を表す構造で、ヒープはそこに優先順位を扱いやすい規則を加えたものです。