: downheap()
: ヒープソート
: ヒープ
目次
索引
レベル 0 から順に配列に詰めていくことで, ヒープを配列で表現
できる. インデックスの対応を分かりやすくするために, 0 番目
でなく 1 番目から詰めることにする. 配列を
とすれば,
レベル 0
個
レベル 1
個
レベル 2
個
レベル
個
と対応する. この表現のもとで, 次が成り立つ.
を要素の個数とする.
を
を越えない最大の整数とする.
問題 13.2 上の性質を証明せよ.
Nobuki Takayama
平成15年9月12日