ヒープソート

平成28年秋季　問6．　ヒープソート

問題文「ヒープソートの説明として、適切なものはどれか。」

解答群
ア．ある間隔おきに取り出した要素からなる部分列をそれぞれ整列し、さらに間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返す。
イ．中間的な基準値を決めて、それよりも大きな値を集めた区分と、小さな値を集めた区分に要素を振り分ける。次に、それぞれの区分の中で同様な処理を繰り返す。
ウ．隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えると言う操作を繰り返す。
エ．未整列の部分を順序木にし、そこから最小値を取り出して整列済みの部分に移す。この操作を繰り返して、未整列の部分を縮めていく。

まずもって名前を知らなければ解けない問題ではある。

まず「ヒープソート」から考えていくが、検索しても「与えられたデータをヒープ構造に追加していき・・・」とか書いてあって、

いやいや、ヒープってそもそもなんだ？( ﾟДﾟ)

と思ってしまうのは俺だけだろうか。

で、ヒープソートを検索していると次のYoutube動画を見つけた
「ヒープソート　byわくわくアカデミー」

ヒープってなに？という疑問には答えてくれなかったが、女性の声が心地よかった。それと視覚的にこういう事するんだなぁということはわかった。

では、ヒープって何？ということで「ヒープとは？」でグーグル先生に聞いたところ、Wikipediaには以下のように書いてあるらしい。

☆ヒープ領域
******************************
ヒープ領域（heap memory）はコンピュータープログラミングにおいて、動的に確保可能なメモリの領域。ヒープ (heap) とは、『山積み』という言葉の中の『山』をさす英単語である。データ構造のヒープと直接的な関係があるかどうかは、ヒープ領域の構造の設計、保守にデータ構造のヒープの技術を使うかどうかに依る。
******************************

上の二つを組み合わせて考えると、スタックのような使い方をしているメモリ上で、大小関係を比較しながらメモリの最上位というか最下位というか端の方から取り出していきながらソート（並び替え）を行うということに見える。

プログラムを作ったらどうだろう？と言う風に考えたが、考えている内に頭がこんがらがってきたので予想だけすると、結局は以下のような形をした「完全二分木」と呼ばれる構造の上と左右をそれぞれ比較しながらソート（並べ替え）を行い、並べ替えが終わったら一番大きい（つまり一番上の値）を取り出して、1番下と交換し、またソートをし・・・
と言うのを繰り返すことで例えば大きい順に並べ替えを行うということだと思われる。


これを一列に並べ替えて、実際の操作を手作業で行ってみると


一番初めにHeap内を整理した後で、一番大きな値を取り除いて再度比較する際、入れ替わった場所だけ比較すれば良さそうなので、1回目と2回目以降のソートは別のループで実現するとわかりやすそうである。
また、2回目以降の操作は入れ替わった値のところだけを見ればよいので、文もそれだけ圧縮できるような気がする。

ここまで考えればなんとなく問題だけは解けそうであるｗ
今日はこのぐらいにしといてやるっ( ﾟДﾟ)