基本情報技術者試験基礎・応用
条件を読む・根拠を説明する
最小ヒープの性質
条件を整理し、答えを選んでから解き方を確認しましょう。
親の値が子以下という最小ヒープから最小値を1つ取り出し、性質を復元した。新しい根について言えることはどれか。
答え・解き方を読む
残る要素の最小値である
考える順序
- 1各親が子以下なら根は全子孫以下
- 2取出し後に同じ性質を復元する
- 3新しい根が残りの最小値になる
選択肢ごとの理由
- 比較 · 残る要素全体が配列順に昇順である
ヒープ条件は全配列の整列を要求しません。
- 比較 · 必ず元の根の左の子である
右の子がより小さい場合もあります。
- 比較 · 残る要素の最大値である
最大値を根に置くのは最大ヒープです。
- 正解 · 残る要素の最小値である
各親が子以下なら根は全子孫以下。取出し後に同じ性質を復元する。新しい根が残りの最小値になる。