ヒープソート (Heap Sort)

バブルソートのような方法では総当たり的に比較を行なっていた． やみくもに最小値を探すことを繰り返し， その過程の比較演算で得られた情報は すべて捨てていた． 時間効率のよいアルゴリズムは，この情報を何らかの方法で ある程度残すことによって，効率を稼いでいる．

ヒープソートではデータ構造として木構造を用いる． 木構造は組織の構成やものの分類などを表現するのに広く用いられる． １冊の本も，章がいくつかあって，各章の中にはいくつかの節があり， その中にまた小節がある，というように木構造をしている． 木構造は，日々目にする通り，節目（ノード）と枝（アーク）からなる． 節目のうち他の枝の先につかないものがひとつあって，これを根といい， その先に枝の出ない節目を葉という． ヒープソートで用いる木構造は，二分木 (binary tree)， すなわち葉でないノードからは1本または2本のアークしか出ないものである． ヒープソートのアルゴリズムは，まず与えられたデータ列を次のような性質をもつ 二分木--ヒープに構成する（図１参照）．

1. 各ノード（根を含む）には，データが１つだけ書いてある．
2. 葉を除く各ノードにおいて， 自分のデータは，その子のデータより，大きくない．

図１．ヒープの例

ヒープを配列で実現する場合は， 各レベル（根をレベル０とし，レベルｎの子ノードをレベルｎ＋１ とする）のノードを左から右に順番に並べた配列とするのがよい． 図１の例では，1, 2, 5, 6, 3, 7, 10, 9, 8, 4 という順番に 並ぶ．

課題６（オプショナル）

注意！この課題はオプショナルである（必修ではない）． 余力のある人，あるいは，興味がある人がトライすること．

課題３のソーティングモジュールをヒープソートによるものに差し替えて動かせ． なお，ヒープを作る関数を，再帰的，非再帰的の両方で書いてみよ．

発展課題として，ヒープソートの時間計算量を考えよ．

この課題を解いた場合の提出方法は以下の通り．

1. Subject: ex1 6th
2. To: ex1kadai-2012@ai.soc.i.kyoto-u.ac.jp
3. Cc: 自分のユーザ名
4. フォーマット
5. 2012 年度の締切は 7/18 (水) とする．

再帰に関する補足

• ひとつのノードは木である．（根だけからなる木．）
• ノードに，１つまたは２つの木をつけたものも，木である．

再帰的関数（モジュール）の例として，階乗を計算する関数（入力が 自然数であることを仮定）をあげておく．

        int	factorial(int n)
        {
                if (n == 0)
                        return(1);
                else
                        return(n * factorial(n-1));
        }

        int     factorial(int n)
        {
                int     pi;

                for (pi=1; n>1; n--)
                        pi *= n;
                return(pi);
        }