【C算法】第6章 ソート (その8)

週の前半は、、、と毎週いっている。なんとかせねば。なんとか生きて乗り切った、という感じ。
さて、木構造が終わったので、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.」
  

のどれでも手をつけられるようになった。
どれからいこうかなぁ。シプサとの関連で、コンパイラにしとこうかな。