ヒープソートの演習第13回 1 課題１ヒープソートのサンプルプログラム（heapsort.pdf参照）は、ヒープソートを用いてデータを降順にソートする．これを実行すると以下のような結果が出力されるこのサンプルプログラムおよび教科書図4.7(p.95)を参考に、次ページの要求を満たすヒープソートのプログラムを作成しなさい 2 課題１の続き・15個の整数 {29, 5, 4, 23, 6, 63, 12, 2, 53, 12, 33, 34, 14, 23, 37} を昇順にソートする。・ソート前のデータ列と、ソート後のデータ列を出力する。・ソート後のデータ列を表示後、プログラム実行時にデータの交換 swap()と最大要素の出力と除去 deletemax()が何回呼び出されたか出力する。・ソースファイル名は、t0629xx_hs.c とする。（t0629xxは自分の学籍番号） 3 課題２・課題１のプログラムを修正して，乱数生成関数rand()を用いて発生させた最大64000個の整数データをソートし，ソートにかかる時間を測定できるようにせよ．（演習I 課題３で学んだclock関数を使用するとよい．) ・データ列は表示しないでよい．・ソースファイル名は，t0629xx_hs2.cとする．・データ数nをいろいろ変えて実行し，各々のnにおいて、ソートにかかる時間が、O(n2)，O(nlogn)，O(n)のどれに近いかを考察せよ。 4 レポートおよび課題の提出・レポート名はt0629xx.docとし、以下の項目を含むこと。・課題１のソースリスト・課題１の出力・課題２のソースリスト・課題２の出力・課題２の考察課題の出力については、出力画面ウィンドウのダンプ、もしくは出力画面からのテキストコピーのどちらでも良い。上記のファイルをコースナビのデータ構造とアルゴリズム（7/23）のレポートとして提出（アップロード）する。〆切： 2008/8/6(水) 18時 5 ヒープソート(heap sort)(p.94)    ヒープを用いてデータの整列を行うアルゴリズム計算量 O (n log n) ヒープ : 配列により半順序木を実現したもの常に子が親より大きい木の例常に子が親より小さい木の例 3 5 6 9 8 10 18 9 9 10 8 10 6 4 1 9 3 2 7 6 6 ヒープソートの原理１．ヒープ（半順序木）を作る（優先度つき待ち行列に入れる）２．以下の処理を繰り返して並べかえる 1. ヒープの先頭の要素と末尾の要素を交換 2. [先頭]～[末尾-１]の部分の半順序を回復させる優先度つきリストＬ２，９，５，６，… 待ち行列９６５２ 7 １．ヒープを作る部分木の根の要素を適切な位置まで下げる操作を繰り返すことで，半順序木をボトムアップに構築する 10 ← a[0] 6 9 5 3 15 18 要素数 n = 15 9 15 8 11 12 9 20 ← a[n/2-1] (=a[6]) a[n-1] (=a[14]) 10 ← 8 ２．並べかえ２－１半順序木の根と右端の葉を交換 3 12 5 6 5 9 8 9 10 10 18 9 15 11 15 20 12 [0] a 6 9 8 9 10 10 18 9 15 11 15 20 3 [n-1] 12 5 9 6 8 9 10 10 18 9 15 11 15 20 3 9 ２．並べかえ（つづき）２－１残りの部分の半順序の回復子が親より小さい間， 2つの子のうち小さい方の子と親を交換していくこの部分のヒープを再構成 [0] [1][2] [3] [4] a 12 5 12 65 9 10 6 8 この部分の半順序を回復させる 12 5 6 9 8 9 10 10 18 9 15 11 15 20 3 [7] [8] [n-2][n-1] 9 10 10 18 9 15 11 15 20 着目する節点の左の子は2*i+1、右の子はそのひとつ後ろにある 3 10 プログラムの概要 begin heapsort heapify １．ヒープ（半順序木）を作る  downMin deleteMin ２．以下の処理を繰り返す 1. downMin 2. end ボトムアップに節点[2/n - 1] ～[0]をしらべ、半順序を満足するように木を作るヒープの先頭の要素と末尾の要素を交換トップダウンに[先頭]～[末尾 -１]の部分の半順序を回復させる 11