データ構造とアルゴリズム
二分ヒープを、根を a[0] とする配列 a[0], a[1], a[2], … に、上の段から順に左から詰めて格納する。a[4] の子と親はどれか。
- A子は a[9] と a[10]、親は a[1]
- B子は a[8] と a[9]、親は a[2]
- C子は a[9] と a[10]、親は a[2]
答えと解説を見る
正解：A. 子は a[9] と a[10]、親は a[1]
根を a[0] とする場合、a[i] の子は a[2i+1] と a[2i+2]、親は a[(i−1)÷2 の切り捨て] です。i = 4 なら子は a[9] と a[10]、親は a[(4−1)÷2] = a[1] です。根を a[1] とする場合は子が a[2i] と a[2i+1]、親が a[i÷2] になるので、どちらの決め方かを確かめることが大切です。このように、ヒープは完全二分木なのでポインタを使わずに配列で表せ、添字の計算だけで親子をたどれます。
- A. 正しい。子は 2×4+1 = 9 と 2×4+2 = 10、親は (4−1)÷2 = 1 です。
- B. 根を a[1] とする決め方の式(子 2i と 2i+1、親 i÷2)を当てはめた結果です。
- C. 子は正しいですが、親は (4−1)÷2 の切り捨てで a[1] です。