平成28年度 秋期 午前 問6

✓ これが正解エ未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。

解説

未整列の部分を順序木にして取り出す方式です。

ヒープソートという名前の中心にあるのは、ヒープ、すなわち順序木という道具です。手順は二つの部分を行き来します。まだ並んでいない部分を順序木の形に組み、その木の根に来る最小値を取り出して、並び終わった部分の末尾へ移します。取り出したあとは木を組み直し、また根から最小値を取ります。これを繰り返すと、未整列の部分が一つずつ縮んでいき、最後にすべてが並びます。木の高さは要素数の対数に比例し、取り出す回数は要素数に等しいので、最悪の場合でも要素数と対数の積に比例する手間で済みます。四つの説明を見分けるときは、それぞれが何を道具にしているかで仕分けると迷いません。木を組むのか、飛び飛びの間隔を縮めるのか、基準値で二つに分けるのか、隣どうしを比べるのかです。設問が問うているのはヒープという名前の方式なので、木を作ると書いてある説明が答えになります。

ほかの選択肢はなぜ違うのか

• アある間隔おきに取り出した要素から成る部分…：間隔をあけて拾った要素だけを並べ、その間隔を段々と詰めていく方式の説明です。扱う道具は木ではなく間隔であり、名前のもとになっている山積みの構造がどこにも現れません。
• イ中間的な基準値を決めて，それよりも大きな…：基準となる値を決め、それより大きい側と小さい側に振り分けてから、区分ごとに同じことを繰り返す方式の説明です。平均的な速さは同じ程度ですが、振り分けてから並べるという筋道が別物です。
• ウ隣り合う要素を比較して，大小の順が逆であ…：隣り合う要素どうしを比べ、順が逆なら入れ替えるという操作を繰り返す方式の説明です。比べる相手が常に隣に限られるため、要素数が増えると手間が二乗に比例して膨らみます。