親の節の値が子の節の値より小さいヒープがある。
このヒープへの挿入は、要素を最後尾に追加し、その要素が親よりも小さい間、親と子を交換することを繰り返せばよい。
次のヒープの*の位置に要素7を追加したとき、Aの位置に来る要素はどれか。
ア | 7 |
イ | 11 |
ウ | 24 |
エ | 25 |
答え イ
【解説】
*の位置に要素7を追加すると
になる。追加した7と親の節25を比較すると、要素7が小さいので交換する。
次に要素7と親の節11を比較すると、要素7が小さいので交換する。
さらに要素7と親の節9を比較すると、要素7が小さいので交換する。
これで、要素7を追加した処理が完了し、Aの位置に来たのは11(イ)である。
【キーワード】
・ヒープ