アルゴリズムとプログラミング
完全二分木に要素を格納したヒープ(最大ヒープ)の性質として、正しいものはどれか。
ア.左部分木のすべての要素が右部分木のすべての要素より小さい。
イ.葉ノードはすべて同じ深さに存在する。
ウ.中間順走査(in-order)で要素が昇順に並ぶ。
エ.親ノードの値は子ノードの値以上である。正解
解説
最大ヒープは「親が子に勝つトーナメント表」。ピラミッドの上に行くほど大きな値が並びます。
なぜ エ が正解か
エが正解。最大ヒープは「親ノード ≥ 子ノード」というヒープ条件を満たす完全二分木で、根が常に最大値になります。優先度付きキューの実装に使われ、最大値取得が O(1)、挿入/削除が O(log n) で行えます。
出典: AI生成問題(学習用)