heap.c

説明を見る。

/**
   @file   heap.c
   @author 学籍番号 氏名
   @date   2009年7月16日
   @brief  ヒープソート

   データを読み込みながらヒープを作成する．
   データの入力を終えると，ヒープからデータを小さい順に取り出し，
   値を表示する．

   @section section1 処理手順
   -# ヒープの初期化   
   -# ヒープの構築
       -  データを読みながらヒープを構築する．
       データを終了したところで処理を終え，次のステップへ
       -# ヒープの後ろにデータを追加
       -# ヒープ条件の調査
            - その値と親ノードの値を比較し，
            - 親ノードの値が小さいか，等しい場合は処理を終える
            - 親ノードが大きい場合は
               -# 値を交換し
               -# 親ノードに移動して,ヒープ条件を調査する
   -# ヒープからデータの取り出し
       -  データが空になるまで以下の処理を繰り返す
       -# ヒープ中の最小値を書き出す
       -# その最小値をヒープから取り除き，
       次の手順でヒープを再構築する
           -# 取り敢えず，ヒープの最後の値を根に移動する
           -# ヒープ条件を満たすまで以下の操作を繰り返す
                -# 左右の子ノートのうち値の小さい方と現在のノードの値を比較する
                -# 現在のノードの値が小さいか等しい場合は，ヒープが成立するので処理を終える
                -# 子ノードの方が小さい場合は，ノードの値を交換し，
                -# 子ノードへ移動して，ヒープ条件を調べる

    @section section2 実行例

    リダイレクション機能を利用して,標準入力に替えてファイルからデータを読み込んで@n
    小さい順に値を書き出す場合を例示する．

    @subsection section2-1 入力
    <pre>
         /.a.out &lt; data1.dat
    </pre>
    @subsection section2-2 出力結果
    <pre>
       0:  32
       1:  45
       3:  52
       4:  60
    </pre>

    @warning このプログラムではエラーに対する配慮がなされていない．\n
    サイズをオーバーした場合や，空のヒープからデータを取り出そうとした場合には segmentation fault が発生する．
*/

/**
  HMAX: ヒープに蓄積可能なデータの容量(個数)
*/
#include <stdio.h>
#define HMAX 100

/**
   @struct heap
   @breif ヒープ

   ヒープ条件を満足する2分木構造

   ヒープ条件: 全てのノードで,その値は子ノードよりも小さいか,等しい

*/
typedef struct {
  int size;        ///< このヒープが持つデータの個数
  int data[HMAX];  ///< データ
} heap;

/**
   @fn    void swap(int *a, int *b)
   @brief 2つの変数の値を交換する
   @param *a [in/out] 変数1 (整数型)
   @param *b [in/out] 変数2 (整数型)
 */
void swap(int *a, int *b) {
  int work = *a;   /// 一時的変数に値を退避する
  *a = *b;
  *b = work;
}

/**
   @brief ヒープ の初期化
   @param ヒープ
*/
void create(heap *h) {
  h->size = 0;           /// 初期値設定： 初期段階ではデータは0個
}

/**
   @brief データの追加
   @param *h [in/out] ヒープ
   @param n [in] 整数値
*/
void insert(heap *h, int n) {
  int i;
  i = h->size;
  h->size++;
  h->data[i] = n;        /**< 仮に,データをヒープの最後に追加する */
  /** ヒープの修正 */
  while((i>0) && (h->data[i] < h->data[(i-1)/2])) {
    swap(&h->data[i], &h->data[(i-1)/2]);   ///< 親ノードと値を交換
    i = (i-1)/2;                            ///< 親ノードへ移動
  }
}

/**
   @brief ヒープが空かどうかを調べる
   @param heap [in]
   @return 空かどうかを論理値で返す
   @retval true このヒープは空である
   @retval false このヒープは空ではない
*/
int isEmpty(heap *h) {
  return h->size == 0;
}

/**
  @brief ヒープ中の最小データの値を返す
  @param heap [in]
  @return ヒープ中の最小値を返す
*/
int findMin(heap *h) {
  return h->data[0];   // 根から値を取り出す
}

/**
   @brief ヒープ中の最小値(根)を取り除く
   @param *h [in/out] ヒープ
*/
void deleteMin( heap *h ) {
  int i, k;
  i = 0;
  /**  - ヒープの最後の値を根に移動する */
  h->data[0] = h->data[h->size-1];
  h->size--;      /** データの個数を1つ小さくする  */
  /**
    - ヒープ条件を満足するようヒープを修正する

    - 子ノードがなくなるまでくり返し,ヒープを辿って下へヒープ条件を調べる
  */
  while( 2*i < h->size ) {
    /**
       - 左右の子ノードのうち，小さい方を選ぶ */
    k = 2*i+1;  /// 左の子ノード
    if((k+1 < h->size) && (h->data[k] > h->data[k+1])) k++;
    if(h->data[i] <= h->data[k]) break;   /// ヒープ条件を満たしたら終了
    /**
       - ヒープ条件を満たすよう,子ノードと値を交換し，
         子ノードより下についても調べる
    */
    swap(&h->data[i], &h->data[k]);
    i = k;
  }
}

/**
 ** @brief ヒープを表示する
 ** @param *h [in] ヒープ
 ** @param pos [in] ヒープ中のノードの位置
 ** @param depth [in] このノードのヒープ中の深さ
 **/
void showHeapSub(heap *h, int pos, int depth) {
  int k, n;
  ///  - 左の子ノードを表示
  k = 2*pos+1;
  if(k < h->size) showHeapSub(h, k, depth+1);
  ///  - 現在の要素の値を表示
  for(n=0; n<depth; n++) putchar('\t');
  printf("%6d\n", h->data[pos]);
  ///  - 右の子ノードを表示
  k++;
  if(k < h->size) showHeapSub(h, k, depth+1);
}

/**
 ** @brief ヒープを表示する
 ** @param *h [in] ヒープ
 **
 **   ヒープを２分木として表示する
 **    実際の処理は showHeapSub 関数で行なう
 **/
void showHeap(heap *h) {
  if(!isEmpty(h)) {
    ///  このヒープの要素数を書き出す
    printf("heap size = %d\n", h->size);
    ///  showHeapSubを用いて,ヒープの先頭からを表示する
    showHeapSub(h, 0, 0);
  }
}

/**
   @brief ヒープを使用したデータのソート

   データを読みながら，ヒープを作成する．

   データが終了すると，ヒープより値の小さい順に
   データを取り出して表示する．
 */
int main(void) {
  heap p;
  int k, n;
  /**
     - ヒープの生成
  */
  create(&p);
  /**
     - データの入力とヒープの構築
  */
  while(scanf("%d", &n) == 1) {
    insert(&p, n);
  }
  /**
     - 小さい順に値を取り出して印刷
  */
  for(k=0; !isEmpty(&p); k++) {
    n = findMin(&p);
    printf("%d: %4d\n", k, n);
    deleteMin(&p);
  }
}

---