n 個の要素をもつ2分ヒープ（最大ヒープ）に、新しい要素を1つ挿入するときの最悪時間計算量はどれか。

解説

正解は「$O(\log n)$」です。ヒープへの挿入では、新しい要素を完全2分木の最後の位置に置き、親より大きい間は親と交換して上へ移動させます。交換は根に達するまでの高さの分しか起こらず、完全2分木の高さは約 ${\log }_{2}n$ なので、最悪でも $O(\log n)$ です。最大値の取り出しも、末尾の要素を根に移して下へ交換していくため、同じく $O(\log n)$ です。「$O(1)$」は最大値を参照する（根を見るだけの）時間です。「$O(n)$」は、整列していない配列から最大値を探す場合などの時間です。「$O(n\log n)$」は、n 個の要素を1つずつ挿入してヒープを作る場合や、ヒープソート全体の時間です。