親の値が子の値以上になる最大ヒープを、根を a[0] とする配列で表している。ヒープ 50, 30, 40, 10, 20, 35 に45を追加する。末尾に置いてから、親より大きい間は親と交換する操作を行った後の配列はどれか。

正解：C. 50, 30, 45, 10, 20, 35, 40

45は a[6] に置かれ、親は a[(6−1)÷2] = a[2] = 40 です。45 > 40 なので交換して a[2] に移ります。次の親 a[0] = 50 は45より大きいので、ここで止まり、50, 30, 45, 10, 20, 35, 40 になります。交換は木の高さの分しか起こらないので追加は O(log n) で、最大値の取り出しも同じく O(log n) です。この性質から、二分ヒープは優先度付きキューの実装によく使われます。

• A. 末尾に置いただけで、親の40より大きいのに交換していません。
• B. 根の50より小さい45を、根まで上げてしまっています。
• C. 正しい。40と交換した後、親の50の方が大きいので止まります。