ヒープソート

計算量

•アルゴリズムの性能を評価するのに「計算量」と

いう概念を用いる

•計算量とは：

–そのアルゴリズムが，おおよそどれだけのステップ数

で実行可能かを表す

–O(n) などのO記号で表す（読み方は，オーダ n）

–ある関数 g(n)がO(f(n))であるとは，次のような条件を

満たすときに成立

g(n) = O(f(n)) ⇔(∃c>0)(∃n0≧0)(∀n≧n0) g(n)≦c・ｆ(n)

ヒープソート

•計算量

–O(n log n)の計算量を持つソートアルゴリズム

–ヒープソートはどんなデータに対してもO(n log n)であ

ることが保証さている

•基本的な考え方

–選択法の改良

n個の値が入った配列 a[n] のソート

for ( i = n - 1; i > 0; i--) {

a[0],...,a[i]の中で最大値を求め， a[p]とする;

a[i]とa[p]を入れ替える;

}

ヒープソートの特徴

•選択法

–各ステップで，最大値を求める操作を繰り返す

–途中で得られる情報を捨てる

→残りのデータの大小関係についての情報を捨て

る

•ヒープソート

–各ステップで，最大値を求める操作を繰り返す

–途中で得られる情報をデータ構造に蓄える

→残りのデータの大小関係の情報をデータ構造の

中に蓄えて，少ない手間で最大値を求める

部分順序付き木

•２分木の構造

•最大値を根ノードに置く

•各ノードの値が，その下の左右2つの子供の値よ

りも大きくなるようにした木（子供同士どちらが大

きいかは問わない）

15 19

10 5

7 18 13 1

図：部分順序付き木の例

部分順序付き木での

最大値の取り出し

•常に，木の根にある値が最大値となる

•最大値を求めるだけなら，O(1)の計算量

•最大値を取り除いた後に，再び部分順序付き木

の条件を満たすように木を作り直すことが必要

20 22

10 5

図：部分順序付き木の組み替え

1. 取り除いた頂点の場所

に左右の子供のうち値の

大きい方を移す．

2. これを木の一番下の段

に達するまで繰り返す

ヒープソートで用いるデータ構造

•部分順序付き木を配列上に表現

具体的なデータ構造の例

–配列の先頭 a[0]に木の根を置く

–それ以外は，頂点 a[i] の左の子供を a[2*i+1]

に右の子供を a[2*i+2] に置く

ヒープの各頂点の添字と配列の対応（n = 10 の場合）

3 4 5 6

7 8 9

0 1 2 3 4 5 6 7 8 9

親子子

親子

ヒープ

•2*i+1 や2*i+2 が配列の要素数を越えている場

合は子がないものと見なす

•配列を隙間なく使う

•ある頂点からその親に行くのも，子に行くのも添

字の計算だけでできる

•配列上に表現した部分順序付き木をヒープと呼

ぶ

ヒープの特徴

•完全二分木の一部のみを表現できる

–一般の「木」を表すことはできない

–葉までの深さが k または k+1のいずれかで，

しかも深さ k+1の葉がすべて左側によせてあ

るもののみ表現できる

ヒープでの最大値の取り出し

1. 最初に，a[n - 1] をa[0] に移動

–取り除いた頂点の代わりに子供を持ってくるだけでは，

完全2分木の形がくずれる

–最初に，配列の最後の要素 a[n - 1] をa[0] に移動して，n

を1減らす

→これで要素数が1減った完全二分木ができる

2. 次に，部分順序木の木の条件を満たすように木の

作り替えを行う

–a[n - 1] をa[0] に移動したときに，部分順序付き木の条

件が満たされていないのは，a[0] とその子供の間だけ

→1点a[k] とその子供の間でだけ条件がくずれているヒー

プを正しく作り直すアルゴリズム： downheap アルゴリ

ズム(入力として k=1, r=n を与える)

DownHeapアルゴリズム

•入力

–k ヒープの条件がくずれている位置

–r 現在のヒープの要素数 - 1

–a データを格納している配列へのポインタ

•計算量

–木の高さが O(log n), 交換一回当たりの手間が O(1)な

ので，全体の計算量は O(log n)

DownHeapアルゴリズム手順

1. j = 2k + 1とする．

2. j ≦r ならば

(a)j≠r ならば

a[j] とa[j + 1]を比較して大きい方を j とする．

(b) i. もし a[k] がa[j] 以上ならば終了．

ii.そうでなければ，a[k]とa[j]の値を入れ替え,

その後 k = j, j = 2k +1 として2.へ

4 5 7 6

1 2 3

4 5 7 6

1 2 3

4 5 5 6

1 2 3

左右の子の大きいほうと交

換する。このいずれも自分

より小さいか、ヒープの底ま

でたどり着いたら終了。

HeapMainアルゴリズムト

•DownHeap を用いて，ヒープソートを行うアルゴリ

ズム

1. i = n - 1とする．

2. i > 0ならば，

(a) a[0]とa[i]の値を入れ替える．

(b) i = i - 1とする．

(d) 2. へ

•ヒープから最大値を取り出して，ヒープの大きさ

を1減らして，DownHeapを用いてヒープを再構築

する，という操作を繰り返す

InitializeHeapアルゴリズム(1/3)

•与えられたデータからヒープのデータ構造

を作るアルゴリズム

–i = [n/2] -1 とする．

–i ≧0ならば

•k = i, r = n-1 として DownHeapを呼び出す

•i = i - 1とする

•2. へ

InitializeHeapアルゴリズム(2/3)

•木を下の方から積み上げていってヒープを完

成させるという方法

•配列の初期状態

–a[n/2], a[n/2 + 1], ... ,a[n-1]は，子供を持たない単

独の頂点

–それぞれ単独では，部分付き順序木の条件を満

足

InitializeHeapアルゴリズム(3/3)

•初期状態を出発点として，全体として１つの木を作る

–木を2つずつ組み合わせる操作を続けて，全体として1つ

の木にを作る（ヒープが完成）

–2. でa[i]を根とする部分木をヒープの条件を満たすように

作り替える

–この時，a[2*i + 1]とa[2*i + 2]をそれぞれ根とする木はす

でに部分ヒープになっている 0

3 4 5 6

7 8 9

2*i+1 2*i+2

図：ヒープの初期化操作

ヒープソートの実現

•ソートすべきデータの，配列への取り込み

•InitializeHeapにより，ヒープを構成

•構成したヒープに，HeapMainを適用

ヒープを作る操作の計算量

•DownHeapで調べる段数：

–iが[n/2]～n の範囲では0段

–[n/4] ～[n/4]の範囲では1段

–[n/8] ～[n/4]の範囲では2段

–全体では

–k = [log n]とするとこの式は次の式の値を越えない

–k =O(log n)なので，この式のオーダはO(n)

0* +1* +2* +・・・+(log n-1)*1

1*2k-2+2*2k-3+・・・+(k-2)*2+(k-1)*1 = 2k-(k+1)

ヒープソートの計算量

•ヒープを作る操作(InitializeHeap)の計算量

–O(nlog n)

•最大値を取り出す操作(HeapMain)の計算量

–O(nlog n)

•ヒープソート全体の計算量

–これらの和： O(nlog n)

サンプルプログラム

/* 0

1 2

3 4 5 6

7 8 9 10 11 12 13 14

#include<stdio.h>

FILE *infile, *outfile;

int tree[10000];

main()

{int i, n, in[20], out[20];

printf("Input InFilename :"); /*入力データのファイル名を入力*/

scanf("%s", in);

if ((infile=fopen(in, "r")) == NULL) {

printf("can't open file %s\n", in);

exit();

}

printf("Input OutFilename :"); /*出力データのファイル名を入力*/

scanf("%s", out);

if ((outfile=fopen(out,"w")) == NULL) {

printf("can't open file %s\n", out);

exit();

}

n=0;

while(fscanf(infile,"%d", &(tree[n])) != EOF) {

n++;

}

InitializeHeap(n);

HeapMain(n);

for (i=0; i<n; i++) {

fprintf(outfile,"%d\n", tree[i]);

}

fclose(outfile);

fclose(infile);

}

HeapMain(int n)

{ /*ヒープソートを行う*/

int i, k, r, tmp;

i=n-1;

while (i>=0) {

tmp = tree[0]; tree[0] = tree[i]; tree[i] = tmp;

i--;

k = 0; r = i;

DownHeap(k, r);

}

InitializeHeap(int n)

{ /*ヒープを構成する*/

int i, k, r;

for (i = n/2-1; i >= 0; i--){

k=i; r=n-1;

DownHeap(k,r);

}

DownHeap(int k, int r)

{ /*ヒープを正しく作り直す*/

int j, tmp;

j = 2*k+1;

while (j <= r){

if ((j!=r) & (tree[j+1]>tree[j]))j=j+1;

if (tree[k] >= tree[j]) {

break;

}

else{

tmp=tree[k]; tree[k]=tree[j]; tree[j]=tmp;

tmp=k; k=j; j=2*tmp+1;

}