課題11　「ヒープソート」

内容

　　ヒープソートを実装しなさい。

　　※ 最大で20個のデータがソートできればよい。（入力データ数は固定してもよい）

　　※ 入力されるデータは正の整数として仮定してもよい。

入力

　　20個の整数値

出力

　　ヒープソートの実行結果（ソートされた20個の整数値）

実行

　　今回は特に値を指定しない。
　　20個の整数値を適当に入力し、実行せよ。

　　※ 大きな値を入れる必要は無いので、入力値 n は、-1000 ＜ n ＜ 1000 程度にすること。

　　※ ソートが正しく行われているかを確認するので、昇順や降順で値を入力することは避けること。

ヒント

出力例

　　入力を赤字で示した。（課題では20個の入力を行うこと）



　　input data
　　-10
　　5
　　-5
　　10
　　-15
　　15
　　5
　　sort data
　　-15 -10 -5 5 5 10 15　

ヒープ

　　ヒープとは、大まかに言えば以下の条件を満たす二分木である。（図1参照。赤い添え字は配列番号に対応）

　　　(1) 木の高さを h とした時、深さ h-1 までは全ての節点が埋まっており、深さ h の葉は左詰で埋まっている。
　　　(2) 親の要素 ＜ 子の要素

　　

　　課題8の二分木や、課題9の二分探索木ではポインタを用いてプログラムを作成したが、ヒープでは配列を用いる。



　　const
	N = 20;
　　var
　　　　Heap : array [1..N] of integer;　


　　今回は、20個のデータがソートできればいいので、N の値は20で良い。

ヒープと配列の対応

　　図1のように、ヒープに対して順番に要素を挿入していくと、親と子には図2のような関係ができる。

　　

　　図1や図2の赤い数字は、要素を格納する配列番号と対応している。
　　つまり、図2の要素を配列に格納するときは以下のようにする。

	Heap[i] = i
	Heap[2i] = 2i
	Heap[2i+1] = 2i+1

　　今回の課題では、ある接点Aの要素と、その親(子)の要素の値を比較する場面が出てくる。
　　特に、親の要素と比較したいときに必要になるであろう小数点切捨ての処理の仕方を以下にあげる。



　　i := 5;

　　write(trunc(i/2));　{出力結果：2}
　　write(i div 2);　　 {出力結果：2}


　　・ 関数 trunc(x) ：実数xの小数部切捨て。
　　・ 演算子 div ：除算の商を整数値で求める。

ヒープソート

　　上述した条件(2)より、ヒープの根には最小要素が格納されている。
　　つまり、根の要素を取り出し続けることで、要素をソートする事が可能である。

　　これを実現する為には、以下の2つの手続きを作成する必要がある。

　　　(ⅰ) INSERT：ヒープに対して新しい要素を挿入する手続き
　　　(ⅱ) DELETEMIN：ヒープの根の要素を削除する手続き

　　INSERTを用いて入力データをヒープに格納し、
　　Heap[1]を出力してDELETEMINを実行する操作を繰り返せばヒープソートは完了する。
　　ただし、どちらの手続きもヒープの条件(1)(2)を満たすように動作しなければならない。

INSERTの実装

　　ヒープに新しく要素 x を挿入する場合。

　　　① 配列の最後尾に x を挿入する。
　　　② x と親の要素と比較し、親の方が大きければ入れ替える。
　　　③ ②を入れ替えが生じなくなるまで繰り返す。

DELETEMINの実装

　　ヒープから根の要素を削除する場合。

　　　① 配列の最後尾の要素を根に移す。(根の要素を上書きする)
　　　② 子の要素のうち小さい方と比較し、親の方が大きければ入れ替える。
　　　③ ②を入れ替えが生じなくなるまで繰り返す。