データ構造(全32問中25問目)

配列内に構成されたヒープとして適切なものはどれか。

出典:平成18年秋期 問 9

  • 09a.gif
  • 09i.gif
  • 09u.gif
  • 09e.gif
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
ヒープ(Heep)は、二分木の1つで「子要素は親要素より常に大きいか等しい(または常に小さいか等しい)」といように、どの親子の節の値についても大小関係が成り立っている木構造です。
09_1.gif
配列をヒープ木に変換する場合、根の要素を配列の添え字1の要素とし、ある要素の左の子「2n」右の子「2n+1」という規則で2分木を構成する方法が一般的です。この方法によると配列の添え字と木構造の位置の関係は次のようになります。
09_2.gif
それぞれの配列を木構造に変換してみると次のようになります。
  • 5と4の間の大小関係が不適切です。
    09_3.gif
  • すべての親子間で大小関係が保たれているので適切です。
    09_4.gif
  • 8と6の間の大小関係が不適切です。
    09_5.gif
  • 6と5の間の大小関係が不適切です。
    09_6.gif

Pagetop