ヒープソートで気がついたこと

勉強会に予習なしで参加してしまったので復習。
特筆することはないけれどPascalの場合、配列の添字が1からsizeという表現のため、
二分木の配列表現がC系とは異なるので注意

例えば、array[i]の子要素はよく

 left: array[i*2]
right: array[i*2 + 1]

と表現される
アルゴリズムの教科書はヴィルト先生の影響でパスカルを使っているものが多いが、これに騙されてはいけない

Cでは添字が0から始まるため、以下のように書かなければいけない

 left: array[(i+1)*2 - 1]
right: array[(i+1)*2]

うーん、これはややこしい。
勘違いに気がつかないままCで書いたプログラムが問題なくソートできていた。

図に書いてみるとわかるけれど、これは平衡木ではないけれど二分木表現として扱うことができるため、downheapがきちんと働いてヒープソートができるためと考えられる。

以下は、{a, b, c, d, e, f}という配列の二分木表現。
左が正しい解釈。右がCにおいてPascalと同様に考えた場合の木の解釈

ちなみに家のマシンにMS Officeが入っていないためOpenOfficeImpressで図を作成したのだけれど、めちゃくちゃ使いづらい
アウトプットとしてはPowerPointと同様のものが作れるのだろうけれど、生産効率を考えたら比ではない。
習熟ってレベルじゃないような気がする。