heap.c

ヒープソート [詳細]

#include <stdio.h>

ソースコードを見る。

構成

struct  heap

マクロ定義

#define HMAX   100

関数

void swap (int *a, int *b)
 2つの変数の値を交換する
void create (heap *h)
 ヒープ の初期化
void insert (heap *h, int n)
 データの追加
int isEmpty (heap *h)
 ヒープが空かどうかを調べる
int findMin (heap *h)
 ヒープ中の最小データの値を返す
void deleteMin (heap *h)
 ヒープ中の最小値(根)を取り除く
void showHeapSub (heap *h, int pos, int depth)
 ヒープを表示する
void showHeap (heap *h)
 ヒープを表示する
int main (void)
 ヒープを使用したデータのソート

説明

ヒープソート

作者:
学籍番号 氏名
日付:
2009年7月16日
データを読み込みながらヒープを作成する． データの入力を終えると，ヒープからデータを小さい順に取り出し， 値を表示する．

処理手順

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

実行例

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

入力

         /.a.out < data1.dat

出力結果

       0:  32
       1:  45
       3:  52
       4:  60

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

heap.c で定義されています。

マクロ定義

#define HMAX   100

HMAX: ヒープに蓄積可能なデータの容量(個数)

heap.c の 60 行で定義されています。

関数

void create ( heap *  h  ) 

ヒープ の初期化

引数:
ヒープ 

初期値設定： 初期段階ではデータは0個

heap.c の 92 行で定義されています。

参照先 heap::size.

参照元 main().

void deleteMin ( heap *  h  ) 

ヒープ中の最小値(根)を取り除く

引数:
*h [in/out] ヒープ

データの個数を1つ小さくする

左の子ノード

ヒープ条件を満たしたら終了

heap.c の 137 行で定義されています。

参照先 heap::data・heap::size・swap().

参照元 main().

int findMin ( heap *  h  ) 

ヒープ中の最小データの値を返す

引数:
heap [in]
戻り値:
ヒープ中の最小値を返す

heap.c の 129 行で定義されています。

参照先 heap::data.

参照元 main().

void insert ( heap *  h,
int  n 
)

データの追加

引数:
*h [in/out] ヒープ
n [in] 整数値

< 仮に,データをヒープの最後に追加する

ヒープの修正

< 親ノードと値を交換

< 親ノードへ移動

heap.c の 101 行で定義されています。

参照先 heap::data・heap::size・swap().

参照元 main().

int isEmpty ( heap *  h  ) 

ヒープが空かどうかを調べる

引数:
heap [in]
戻り値:
空かどうかを論理値で返す
戻り値:
true このヒープは空である
false このヒープは空ではない

heap.c の 120 行で定義されています。

参照先 heap::size.

参照元 main()・showHeap().

int main ( void   ) 

ヒープを使用したデータのソート

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

データが終了すると，ヒープより値の小さい順に データを取り出して表示する．

heap.c の 206 行で定義されています。

参照先 create()・deleteMin()・findMin()・insert()・isEmpty().

void showHeap ( heap *  h  ) 

ヒープを表示する

引数:
*h [in] ヒープ
ヒープを２分木として表示する 実際の処理は showHeapSub 関数で行なう

このヒープの要素数を書き出す

showHeapSubを用いて,ヒープの先頭からを表示する

heap.c の 189 行で定義されています。

参照先 isEmpty()・showHeapSub()・heap::size.

void showHeapSub ( heap *  h,
int  pos,
int  depth 
)

ヒープを表示する

引数:
*h [in] ヒープ
pos [in] ヒープ中のノードの位置
depth [in] このノードのヒープ中の深さ

heap.c の 169 行で定義されています。

参照元 showHeap().

void swap ( int *  a,
int *  b 
)

2つの変数の値を交換する

引数:
*a [in/out] 変数1 (整数型)
*b [in/out] 変数2 (整数型)

一時的変数に値を退避する

heap.c の 82 行で定義されています。

参照元 deleteMin()・insert().

Mon Jul 13 18:02:32 2009に生成されました。  doxygen 1.4.7