ヒープソート

1. ヒープ・ソートの特長
   ヒープは、親が子供より大きくなるよう配置された木構造で、木の根は最大値になります。ヒープソートはこのヒープの特長を利用した高速な整列法です。
   
   
2. ヒープ構造
   
   1. ヒープの例
      ヒープは図のように、子供より親の値が大きくなっている木構造です。例えば、62の子供は52と45で、親は子供より大きな値です。左右の子供の大小関係はありません。
      
   2. ヒープのデータ形式
      ヒープは最終段を除き左右のバランスがとれた構造ですから、配列を利用して簡単に記録できます。要素１の子供を2,3に、2の子供を4,5に、記憶します。一般に、iの要素の子供を2*iと2*i+1の要素に記録します。
      　この方法では、配列0の要素は利用できませんから注意して下さい。
      
      
   3. ヒープに変換する
      配列のデータをヒープにするには、一番下の段から始めて、子供より親の値が大きくなるように入れ替えて行きます。データの数をn、配列をAとするととすると、最後の親はA[n/2]の要素です。親と子供を比べて、親より大きい子供がいれば、大きい方の子供と親を入れ替えます。この操作を、最後の親から順に遡って、先頭の親まで行います。
      　注意すべきことは、親と子供を入れ替えた場合、入れ替えて子供になったかっての親が、さらに下の子供より大きいか調べ、必要なら入れ替えを行う必要があることです。
      
      
   4. 整列する
      
      　ヒープ構造になった配列は先頭に最大値があります。これを、配列の最後の要素と入れ替えます。次にデータの個数を　n-1　とし、入れ替わった先頭の親a[1]を、子供と比較して、ヒープを再構成します。この操作が終了すると、a[1]には、n-1個のデータの中の最大値が残ります。
      　この操作を繰り返せば、後ろから順に大きな数が整列します。
      
      
3. プロジェクト
   
   1. 部品配置
      データの個数を設定する　文字入力ボックス、整列データを表示する文字表示欄、整列を開始するボタンを配置します。
      
   2. ボタン処理
      　データの個数をnumに読みとり、乱数を利用して配列data[]に整数データを記録します。このとき、データはdata[1]からnum個記録します。data[0]は利用できません。
      
   3. Shift()メソッド
      data[L]の要素をdata[R]までの範囲で、ヒープ構造にします。data[L]と子供を比較し、子供の法が大きければ大きい方の子供と親を交換します。交換された子供は、さらに次の段の子供と比較し、必要なら子供と入れ替えます。
      

        void Shift(int L,int R){
          int i,j;
          int x;
          boolean Cont;
          i=L;
          j=2*i;
          Cont=true;
          x=data[i];
          while( j <= R && Cont){
            if (j < R)
              if (data[j] < data[j+1]) j++;
            if( x >= data[j]) Cont=false;
            else {
                data[i]=data[j];
                i=j;j=2*i;
              }
          }
          data[i]=x;
        }

   4. 整列する
      まず、配列全体をnum/2の要素から順に、ヒープ構造にします。次に、data[1]とdata[R]を入れ替え、Rの値を１減らしてからヒープを再構成します。
      

        void HeapSort(int data[],int num){
          int L,R;
          int x;
          L=num/2+1;
          R=num;
          while(L>1){
            L--;
            Shift(L,R);
          }
          st+="ヒープ\n";
          print(data,num);
      
         while(R>1){
            x=data[1];
            data[1]=data[R];
            data[R]=x;
            R--;
            Shift(L,R);
          }
          st+="整列\n";
          print(data,num);
        }

      
      
   5. 表示
      文字列stに、最初の配列、ヒープ構造にした配列、整列した配列、を記録し、表示します。
      
      
   
   
4. 実行
   実行するデータの個数を入力し、実行ボタンを押します。
   
   
   
   
5. ダウンロード
   このプロジェクトをダウンロードできます。次の行をクリックして、heapsort.exeファイルを適当なフォルダに保存します。
   ダウンロード開始
   このファイルは自己解凍型の圧縮ファイルです。このファイルを実行すると指定したフォルダに必要なファイルが生成されます。