/**
@file heap.c
@author 学籍番号 氏名
@date 2009年7月16日
@brief ヒープソート
データを読み込みながらヒープを作成する．
データの入力を終えると，ヒープからデータを小さい順に取り出し，
値を表示する．
@section section1 処理手順
-# ヒープの初期化
-# ヒープの構築
- データを読みながらヒープを構築する．
データを終了したところで処理を終え，次のステップへ
-# ヒープの後ろにデータを追加
-# ヒープ条件の調査
- その値と親ノードの値を比較し，
- 親ノードの値が小さいか，等しい場合は処理を終える
- 親ノードが大きい場合は
-# 値を交換し
-# 親ノードに移動して,ヒープ条件を調査する
-# ヒープからデータの取り出し
- データが空になるまで以下の処理を繰り返す
-# ヒープ中の最小値を書き出す
-# その最小値をヒープから取り除き，
次の手順でヒープを再構築する
-# 取り敢えず，ヒープの最後の値を根に移動する
-# ヒープ条件を満たすまで以下の操作を繰り返す
-# 左右の子ノートのうち値の小さい方と現在のノードの値を比較する
-# 現在のノードの値が小さいか等しい場合は，ヒープが成立するので処理を終える
-# 子ノードの方が小さい場合は，ノードの値を交換し，
-# 子ノードへ移動して，ヒープ条件を調べる
@section section2 実行例
リダイレクション機能を利用して,標準入力に替えてファイルからデータを読み込んで@n
小さい順に値を書き出す場合を例示する．
@subsection section2-1 入力
<pre>
/.a.out < 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);
}
}