さて、木構造が終わったので、6-8 ヒープソート。。。
順序木 ：兄弟の間に順序関係を有する木。
無順序木 ：兄弟の間に順序関係を有しない木。
２進木 ：度数がたかだか2の木。
２分木 ：兄弟に左右の区別がある2進木。
完全２分木：根から下方へむかって、同一レベルでは左から順に詰められている2分木
２分探索木：ノードの値とくらべて、左部分木の値は小さく、右部分木の値は大きい。
ヒープ ：親の値が子の値以上になっている完全2分木。兄弟の大小関係は任意。
半順序木 ：ヒープの別名。- 完全２分木に配列の要素をわりあてたときの様相。
a[i]の親はa[(i - 1) / 2]
a[i]の左の子はa[i * 2 + 1]
a[i]の右の子はa[i * 2 + 2]
なんで？？ - ためす。
1の親は、(1 - 1)/2 = 0
1の左の子は、1 * 2 + 1 =3
1の右の子は、1 * 2 + 2 =4
2の親は、(2 - 1)/2 = 0
2の左の子は、2 * 2 + 1 =5
2の右の子は、2 * 2 + 2 =6
3の親は、(3 - 1)/2 = 1
3の左の子は、3 * 2 + 1 =7
3の右の子は、3 * 2 + 2 =8
4の親は、(4 - 1)/2 = 1
4の左の子は、4 * 2 + 1 =9
4の右の子は、4 * 2 + 2 =10
たしかにそうなっている。なんでこうなるの? - まず、heapを階層毎にグループにわけると、
{{0},{1,2},{3,4,5,6},{7,8,9,10,11,12,13,14},...}
となる。法則性はある。。。かんがえる。。。 - a[n]の子まで添字をふるには、まず、a[n]の階層の残りのノードと、既存のノード*2だけノードを処理する必要がある。
ところで、木の左端の要素の系列は階層で上から下にならべると、a[0],a[1],a[3],a[7],a[15],...となる。これは(2^n) - 1である(n = 0,1,2,...)。
一方各階層のノード数は、2^n (n=0,1,2,...)である。
すると、a[(2^n) - 1]の子供に辿りつく前に添字をふるべきノードは同じ階層の残りだから、(2^n)-1個ある。ゆえに左端のノードについてはa[i]の子のノードがa[i*2 + (1 or 2)]というのはなりたっている。
つぎに2^n個の階層のノードで、(2^n)-1から数えてたどりつくまでにp個のノードを経るような(p=[0,(2^n)-1])ノードに着目しよう。すなわち、(2^n)-1+pという添字のノードだ。
さて子のノードに辿りつくまでに添字をふるべきノードの数は、同じ階層で、(2^n)-p個ある。ひとつしたの階層でもふるべきであり、同じ階層でその対象となるのは、p個だから、2*p個の添字をふる。よって、ふられる添字は、(2^n) - p + 2*p = (2^n)+p。
さて、親の添字は、(2^n)-1+pであり、子の一歩のノードの添字は、(2^n)+p-2+(2^n)+p=2((2^n)-1+p)だから、これもa[i]の子がa[i*2 + ( 1 or 2)]というのがなりたつ。■
これで親から子はわかった。 - 子から親は、親から子を逆転させればOK。
- これで、heapというデータ構造を配列で実現できることがわかった。
- あとはちょいちょい。
おお！ついに「新版C言語によるアルゴリズムとデータ構造」を読了した！
これで、
- 「例解UNIXプログラミング教室」
- 「アルゴリズムC」
- 「新コンピュータサイエンス講座 コンパイラ」
- 「Operationg Systems Design and Implementation 3rd Ed.」
のどれでも手をつけられるようになった。
どれからいこうかなぁ。シプサとの関連で、コンパイラにしとこうかな。
