3. 以下のような条件 (A), (B) を満たす2分木を考える.
(A) 子節点が存在する全ての節点について, その節点の値が子節点の値より大きいか等しい.
(B) 一番深いレベル以外は節点が全て詰まっており, 一番深いレベルでは節点が左に詰まって
いる.
このような木を以下ではヒープ木と呼ぶ. ヒープ木を幅優先で左から走査しながら節点の値を順番に格納
した配列を以下ではヒープ配列と呼ぶ. 配列の添字は0から始まるものとし, n個の要素からなる配列♭を
b[0.n-1] と表記する. 図 3.1 は, ヒープ木の例とそれに対応するヒープ配列 c[0..9] である.
1) b[0.n-1] ヒープ配列として, それに対応するヒープ木をTとする.
a) T の高さを h とするとき, n の最大値をnで表せ.ここで木の高さとは, 根節点と一番深いレベ
ルの節点間にある枝の数とする. 例えば,図 3.1 のヒープ木は高さ3である.
b) Tにおいて節点p の左の子節点をq,右の子節点をェとし, p, q, r がそれぞれ b[s],b[t],
b [u] に対応するとき, tとusで表せ.
c) b[0.n-1] におけるn個の要素が相異なる値を持ち、その最大値と最小値を持つ要素をそれぞ
れ b [v], b [w] とするとき, v と w それぞれの値もしくは値の範囲を答えよ.
