ヒープの配列による表現

レベル 0 から順に配列に詰めていくことで, ヒープを配列で表現 できる. インデックスの対応を分かりやすくするために, 0 番目 でなく 1 番目から詰めることにする. 配列を $A$ とすれば,

レベル 0 		 $A[1]$ $2^0$ 個 

レベル 1 		 $A[2], A[3]$ $2^1$ 個 

レベル 2 		 $A[4], A[5], A[6], A[7]$ $2^2$ 個 

		 $\ldots$

レベル $k$ $A[2^k], A[2^k+1], \ldots, A[2^{k+1}-1]$ $2^k$ 個

と対応する. この表現のもとで, 次が成り立つ. $N$ を要素の個数とする. $\lfloor x \rfloor$ を $x$ を越えない最大の整数とする.

• レベル $k$ までの要素の個数は $1+2+2^2+\ldots+2^k = 2^{k+1}-1$ 個.
• レベル $k$ の $l$ 番目のノードは $A[2^k-1+l]$.
• 子があるノードは $A[1], \ldots, A[\lfloor N/2 \rfloor]$.

• $A[I]$ の子は $A[2I]$, $A[2I+1]$ (もしあれば).

• $A[I]$ の親は $A[\lfloor I/2 \rfloor]$

問 18.1   上の性質を証明せよ.