HOME»ソフトウェア開発技術者平成16年春期»午前問12
ソフトウェア開発技術者平成16年春期 午前問12
問12
与えられた1～8の整数の列をヒープソートによって降順に並べ替えるため，列の全体をヒープに構成したところ，
1，4，2，5，8，3，6，7
となった。ここで先頭の要素と最後の要素を交換して7，4，2，5，8，3，6，1
とし，次に下線の部分をヒープに構成する手続を実行する。このとき，実行直後の列はどうなるか。ここでヒープは列の1番目(左端)の要素が根，列のi番目の要素の子が2i番目と2i＋1番目の要素と見なした完全2分木上に構成されるものとする。- 2，4，3，5，8，7，6，1
- 4，2，5，8，3，6，7，1
- 7，4，5，8，3，6，2，1
- 8，7，6，5，4，3，2，1
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ア
解説
ヒープ木は、親の値は子の値以上（または以下）という規則を保つように各要素が配置される木構造で、ヒープ木の根には、全要素の中で最も大きい（または小さい）要素がくることになります。ヒープソートは、このヒープ木の性質を利用して、①ヒープ木の根の要素を取り出して整列済要素に追加する、②ヒープ木を再構成するという2つの操作を繰り返して整列を行うアルゴリズムです。
設問の「列の1番目(左端)の要素が根，列のi番目の要素の子が2i番目と2i＋1番目」という条件で各要素を完全二分木にする場合、整数列上における各要素の順番と木構造上での配置は以下のように対応します。
設問のヒープソートでは最初に最小値の"1"を取り出しているため、次に取り出すべきはその次に小さい"2"です。したがって、ヒープ木の性質を満たし、かつ、"2"が根の位置にきている「ア」が正解となります。
設問の「列の1番目(左端)の要素が根，列のi番目の要素の子が2i番目と2i＋1番目」という条件で各要素を完全二分木にする場合、整数列上における各要素の順番と木構造上での配置は以下のように対応します。
- 正しい。全ての要素が「親の値≦子の値」なのでヒープ木の性質を満たし、かつ、"2"が根の位置にきていいます。
- 未整列の要素のうち最大値でも最小値でもない"4"が根の位置にきているので、ヒープ木の性質を満たしません。
- 未整列の要素のうち最大値でも最小値でもない"7"が根の位置にきているので、ヒープ木の性質を満たしません。
- 全ての要素が「親の値≧子の値」なのでヒープ木の性質を満たしていますが、取り出したい要素は、未整列の要素のうち最も小さい"2"なのでヒープ木の構成が逆順です。
