アルゴリズムとデータ構造

(1)

アルゴリズムとデータ構造

2012 年 7 月 2 日

酒居敬一 ([email protected])

http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html

1

(2)

ヒープソート（１８５ページ）

0 i length-1

ソート済みソート前

挿入法では、ソート未完了の列から線形探索により次の挿入対象を探していた。

配列

[i]

の位置に、配列

[0]

から配列

[i]

までの間の

最大値を置くことを、配列末端から繰り返せばソートできる。

ただし、線形探索を毎回繰り返すのは効率が悪い。

(3)

部分順序付き木（１８６ページ）

3

5 13 3

9 17 15

21

1 11 7

19 23

• 

挿入法におけるソート前データ列から探索しやすいように

データの置き方を工夫する。これまでの探索木のような順序木ではなく、

部分順序付き木というものにデータを置く。

• 

データを置くルールは、親の値が子の値より小さくないこと。

• 

そうすると、根には最大値が来る。

二分探索木ではないので、

このような配置でも問題ない

(4)

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

a

f b e

b a ≤

c

a b

d

b a >

f e ≤ d

c >

c

a

b d

b a >

a

b

f e

b

a ≤

(

原理的

•187

ページ

)

(5)

ソートのための部分順序付き木

5

5 13

3 9

17 15

21

1 11 7

19 23

• 

ソートのために特別なデータ構造を定義し使用することは非効率。

• 

これを配列に置くことを考える。

• 

木の高さがバランスしていないとソート途中の探索も非効率。

• 

配列上のデータの並びから、一律に木の形を定義する。

• 

配列

[i]

の子は、根を配列

[0]

とすると、配列

[2*i+1]

配列

[2*i+2]

になる。

• 

教科書と違うことに注意。

11 10

9 8

7

6 5

4 3

2 1

0

(6)

17 9

21 23

13 19 5 11 7 3 1

配列に木を表現したことにする（１８８ページ）

15 17 9

21 23 13

11 5 7

3

19 1 15

根２段目３段目４段目木にバランスよくデータを置くには

配列上にあるデータ列を区切って木に対応付けるとよい。

でも、部分順序付き木ですらない。

（このページの現状では

…

）

(7)

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

7

f e

c

a b

d

(

ソート目的

•190

ページ

)

木のバランスを崩さないように頂点ｆを根に動かした。

根を取り除いた。

f d >

d c ≤

e c

f

a

b d

e c

d

a

b f

根は配列

[0]

、

f

は配列の最後にある。

b a >

e c

a

f

b d

f a >

a

と

f

を入れ替え

d

と

f

を入れ替え

(8)

最初のヒープを作る

（１８９ページから１９１ページ、手続き

downheap

）

17 9

21 23

13 19 5 11 7 3 15 1

17 9

21 23 13

11 5 7

3

19

1 15 5

23 15

17 11 9

21 23 19 15 7 3 13 5 1

9 17

3 17 23 9 5

9 17

23 5 21

3 15

21 23

9 17

13 5 23

11 21 7

3

19 1 15

13 23

9 17

21 5 23

11 13 7

3

19 1 15

21 13

9 17

21 5 23

11 15 7

3

19 1 13

13 15

配列にデータを置いているので、

葉とその親の位置は計算で一意に求まる。

そこで、葉に近いところから、

部分順序付き木のルールに従ってデータをそろえていく。

（１９２ページ）

(9)

9

5 13

3 9

17 15

21

1 11 7

19 23

17 9

11 3 5 7 1 19 21 23

13 15 9 11 1 3 5 7 17 19 21 23

13 15

17 15 21 11 17 9 13 11 5 7 1 9 3 19 21 23 23 17 19 11 9 15 5 7 7 3 3 13 21 23 5 1

19 17 9 15 11 1 13

21 19 15 7 1 3 13 5 23

5 13

3 9 15 17 21

1 11

7 19 23

5 13

3 9

17

15

21

1 11 7

19 23

5 13

3 9

17

15

21

1

11 7 19

23 5 13

3 9

17 15

21

1

11

7 19 23

5 13

3 9

17

15

21

1

11

7 19 23

5 13

3 9

17 15 21

1

11

7 19 23

5 13

3 9

17 15 21

1

11

7 19 23

17 9

11 7 1 3 5 13 15 19 21 23

5

13

3

9

17 15 21

1

11

7 19 23

17 9 5 7 1 3 11 13 15 19 21 23

5

13

3 9 15 17 21

1

11

7 19 23

17 9 11 21 23

5 7 3 1 13 15 19

5 13

3 9 15 17 21

1

11 7 19 23

17 9 11 21 23

5 1 3 7 13 15 19

5 13

3 9 15 17 21

1

11 7 19 23

17 9 11 21 23

5 7

3 1 3 5 7 9 11 13 15 17 19 19 21 23

1 13 15

17 9 11 21 23

5 7

3 19

1 13 15

最大値を部分順序付き木から

探しながら挿入法のようにソート（１９２・１９３ページ）

1.  

最大値をソート済み列に加える。

2. 

未ソートデータ列の最後のデータを根に置く。

3. 

部分順序付き木になるようにデータを移動する。

(10)

public class HeapSort {

private final static <E extends Comparable<E>> int downheap(E[] array, int root, int last){

int n = 0;

E v = array[root];

while(true){

int j = 2*root+1; // 左の子

if(j > last) break; // 左の子がない(もちろん、右にも子がない)場合は終了 if(j != last){ // 両方の子がある

n++;

if(array[j+1].compareTo(array[j]) > 0) j++; // 右の子 > 左の子、大きいほうを選ぶ }

n++;

if(v.compareTo(array[j]) >= 0) break;

array[root] = array[j];

root = j; // 上→下 }

array[root] = v;

return n;

}

public static <E extends Comparable<E>> int sort(E[] array) { int n = 0;

for(int i = array.length/2 - 1; i >= 0; i--) n += downheap(array, i, array.length - 1); //下→上 for(int i = array.length - 1; i > 0; i--){

E temp = array[0]; array[0] = array[i]; array[i] = temp;

n += downheap(array, 0, i-1);

x

の子は

2*x+1

と

2*x+2

にあるので、

length

が奇数なら、

2*x+2=length-1, x=(length-3)/2

length

が偶数なら、

2*x+1=length-1, x=(length-2)/2

(11)

兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 18

0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 66

private final static String[] test_data_string = {

"東京", "北海道", "高知", "兵庫", "鹿児島", "沖縄", "青森"};

private final static Integer[] test_data_int = { 47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10};

public static void main(String[] args) { int n;

StringBuffer sb = new StringBuffer();

String[] data1 = test_data_string.clone();

n = sort(data1);

for (String e : data1) {

sb.append(e).append(", ");

}

sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n');

Integer[] data2 = test_data_int.clone();

n = sort(data2);

for (Integer e : data2) { sb.append(e).append(", ");

}

sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n');

System.out.print(sb.toString());

}

11

(12)

ヒープソートの計算量 (193

ページ

)

•   完全２分木とすると、 downheap で調べる

段数は、部分木の範囲ごとに次のようになる。

•   全体では、

•   とすると

だったので、

初期操作には O(n) 必要。

1

段

n/4

から

n/2 2

段

n/8

から

n/4 3

段

n/16

から

n/8 4

段

n/32

から

n/16

1 ) 1 32 (log

16 4 8 3

4 2

1 × n + × n + × n + × n + +

₂

n − ×



⎡ ⁿ ⎤

k = log

₂

) 1 (

2 1 ) 1 (

2 ) 2 (

2 3 2

2 2

1 ×

^k⁻²

+ ×

^k⁻³

+ ×

^k⁻⁴

+  + k − × + k − × =

^k

− k +

) (log

₂

n O

k = ^O ⁽ⁿ ⁾

(13)

ヒープソートの計算量

^{（つづき）}

•   最大値を一つづつ取り出して、ソートする作業では、

最大値を取り出す作業が回

その後で木を作り替える作業が回つまりになる。

13

n

2 n log

) log

( n n

O

(14)