2分ヒープを配列 A[0], A[1], … に格納するとき、A[i] の節点の左の子と右の子の添字の組合せとして適切なものはどれか。ここで、添字は0から始まり、根は A[0] とする。

解説

正解は「2i+1 と 2i+2」です。2分ヒープは完全2分木なので、根から順にレベルごとに左から詰めて配列に格納すると、ポインタを使わずに親子関係を添字の計算だけで表せます。添字が0から始まる場合、A[i] の左の子は A[2i+1]、右の子は A[2i+2] で、例えば根 A[0] の子は A[1] と A[2] になります。「2i と 2i+1」は、添字を1から始めた場合の式で、0から始めると根 A[0] の左の子が A[0] 自身になってしまいます。「i+1 と i+2」は隣の要素を指すだけで、木の構造を表しません。「2i−1 と 2i」では、根の左の子の添字が負になります。