データ構造 (全40問中33問目)
No.33
配列内に構成されたヒープとして適切なものはどれか。
出典：平成18年秋期 問9
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
イ
解説
ヒープ(Heep)は、二分木の1つで「子要素は親要素より常に大きいか等しい(または常に小さいか等しい)」といように、どの親子の節の値についても大小関係が成り立っている木構造です。
配列をヒープ木に変換する場合、根の要素を配列の添え字1の要素とし、ある要素の左の子「2n」右の子「2n＋1」という規則で2分木を構成する方法が一般的です。この方法によると配列の添え字と木構造の位置の関係は次のようになります。
それぞれの配列を木構造に変換してみると次のようになります。
- 5と4の間の大小関係が不適切です。
- すべての親子間で大小関係が保たれているので適切です。
- 8と6の間の大小関係が不適切です。
- 6と5の間の大小関係が不適切です。
