Javaでヒープソートのコーディングメモ

/**
Javaでのヒープソートの実装。
 ヒープソートの計算時間:O( N log<sub>2</sub> N )
 クイックソートよりは平均で若干遅いが,オーダー的には同じ。
 また,クイックソートは,最悪時間が O( N<sup>2</sup> ) となるが,
  ヒープソートは常にO( N log<sub>2</sub> N ) となるので,安定している。
*/

class HeapSort
{
 public static int getPa(int n) { // nの親を取得
  return (n-1)/2;
 }
 public static int getChLeft(int n) { // nの右の子を取得
  return 2 * n + 1;
 }
 public static int getChRight(int n) { // nの左の子を取得
  return 2 * n + 2;
 }

 public static void show(int a[]) {
  for(int i = 0; i < a.length; i++) {
   System.out.print(a[i] + " ");
  }
  System.out.println();
 }

 public static void main(String args[])
 {
  int a[] = {8,15,3,1,10,2,5};
  int i, w;
  int maxv, pa;
  System.out.println("初期値");
  show(a);
  // とりあえず,配列をヒープの状態にする

  for(i = a.length - 1; i >= 1; i--) { // 最初は後ろから順に見ていく。2つづつiを減らすのは,子供が2つづつ一度に見るため。
   pa = getPa(i);
   if(i % 2 == 0)
   {
    if(a[i-1] > a[i]) { // 左の子 > 右の子 2つの子供の大きさを比較。大きいほうを maxv に入れて親を入れ替える
     maxv = i - 1;
    } else {
     maxv = i;
    }
    i--;
   } else {
    maxv = i;
   }

   // 2つの子供で,大きいほう maxv 大きいほうと親を入れ替える
   if(a[ pa ] < a[maxv]) {
    // a[pa] と a[maxv]の値を入れ替える作業
    w = a[ pa ];
    a[ pa ] = a[maxv];
    a[maxv] = w;
   }
  }
  System.out.println("後ろから順に,ヒープの初期化1");
  show(a);

  int right, left;
  for(i = 1; i < a.length; i++) { // 親子孫関係の確認を行う
   left = 2*i+1; // 左の子供
   right = 2*i+2; // 右の子供
   if(left < a.length) { // 左の子供がいるか確認すること
    if(right < a.length) { // 右の子供がいるか確認すること
     if(a[left] > a[right]) { // 左の子の方が右の子より大きい
      maxv = left; // 大きいのは左の子
     } else {
      maxv = right; // 大きいのは右の子
     }
    } else {
     maxv = left; // 左の子供しかいない
    }
    if(a[i] < a[maxv]) {// 自分より,子供の方が大きい(子供と入れ替え)
     // a[i]とa[maxv]を入れ替える
     w = a[i];
     a[i] = a[maxv];
     a[maxv] = w;
    }
   }
  }
  System.out.println("親子関係確認完了");
  show(a);
  System.out.println("ヒープソート準備完了");
  // 第一段階完了
  // 第二段階開始
  for(int x = 1; x < a.length; x++) { // 後ろのヒープソート要素範囲を減らすループ
   /* 先頭(最大値)と,一番後ろを入れ替える(並べ替えが完了しているデータ) */
   w = a[a.length - x]; a[a.length - x] = a[0]; a[0] = w;
   show(a);
   for(i = 0; i < a.length - x; i++) { // 先頭から,ヒープソートをする
    left = 2*i+1; // 左の子供
    right = 2*i+2; // 右の子供
    if(left < a.length - x) { // 左の子供がいるか確認すること
     if(right < a.length - x) { // 右の子供がいるか確認すること
      if(a[left] > a[right]) { // 左の子の方が右の子より大きい
       maxv = left; // 大きいのは左の子
      } else {
       maxv = right; // 大きいのは右の子
      }
     } else {
      maxv = left; // 左の子供しかいない
     }
     if(a[i] < a[maxv]) { // 自分より,子供の方が大きい(子供と入れ替え)
      w = a[i]; a[i] = a[maxv]; a[maxv] = w;// 子供と値を入れ替える
     }
    }
   }
  }
  System.out.println("完了");
  show(a);
 }
}

この記事へのコメント

この記事へのトラックバック