メインコンテンツへ
アルゴリズムとプログラミングアルゴリズムとデータ構造

完全二分木に要素を格納したヒープ(最大ヒープ)の性質として、正しいものはどれか。

ア.左部分木のすべての要素が右部分木のすべての要素より小さい。
イ.葉ノードはすべて同じ深さに存在する。
ウ.中間順走査(in-order)で要素が昇順に並ぶ。
エ.親ノードの値は子ノードの値以上である。正解

解説

最大ヒープは「親が子に勝つトーナメント表」。ピラミッドの上に行くほど大きな値が並びます。

なぜ エ が正解か

エが正解。最大ヒープは「親ノード ≥ 子ノード」というヒープ条件を満たす完全二分木で、根が常に最大値になります。優先度付きキューの実装に使われ、最大値取得が O(1)、挿入/削除が O(log n) で行えます。

なぜ ア は間違いか

左部分木 < 右部分木という性質をもつのは「二分探索木」の…ですらなく、それでも一致しません(BSTは左<親<右)。ヒープには左右の大小制約は存在しません。

なぜ イ は間違いか

すべての葉が同じ深さにあるのは、完全二分木のさらに特殊な場合です。ヒープで使う完全二分木は最下段が左詰めであればよく、すべての葉が同じ深さである必要はありません。

なぜ ウ は間違いか

中間順走査で昇順になるのは二分探索木の性質。ヒープでは中間順走査をしても整列されません——「最大ヒープなら降順では?」も誤りで、走査順と整列は無関係です。

出典: AI生成問題(学習用)