2004/10/22
ソフトウェア概論 (Fortran)

ヒープ法による数値データの並びかえ

# 本実は、Fortran の話ではなく、アルゴリズムや、データ構造の話

==

Tree 構造
	節 (ふし : 図の○の部分 : Node )
	枝 (えだ : 図の○のを結ぶ部分 : Arc )

	枝で結ばれた二つの節
		上の節 : 親
		下の節 : 子
		同じ親を持つ節同士 : 兄弟
		親を持たない節 : 根 ( ね、こん, Root )
		子を持たない節 : 葉 ( は, Leaf )
		特定な節から下の部分 : 部分木

子の数が、2 以下 ( 0, 1, 2 の場合がありうる ) の場合の木 : 二分木

==

ヒープ法では、二分木を利用する
	節の値が子が親より大きい様な二分木を利用する

==

二分木は、添字の対応関係を利用することによって、配列上に作ることができる
	Root = 1
	子の添字 : 親の添字 x 2, 親の添字 x 2 + 1
	親の添字 : 子の添字 / 2 ( 整数計算 )

# この対応によって、M = 2^N - 1 の子を持つ木は、最良で、M のサイズ配列、
# 最悪で、2^M - 1 のサイズの配列が必要になる。

M = 15 場合

[最良]
	1
	|   \
	2       3
	|  \    |  \
	4   5   6   7
	|\  |\  |\  |\
	8 9 1 1 1 1 1 1
            0 1 2 3 4 5

[最悪]

	1          = 2^1 - 1
         \
	  3        = 2^2 - 1
           \
	    7      = 2^3 - 1
             ..
              \
	           = 2^15 - 1

# ヒープ法では、常に、最良の状況で利用する所がポイント

==

課題は、sift subrouting を作成すること

     sift(a,l,r)
	a(l+1) から a(r) までがヒープであるとき
		=> a(l) をこれらい加えて
			a(l) から a(r) をヒープにする