親の節の値が子の節の値より小さいヒープがある。
このヒープへの挿入は、要素を最後尾に追加し、その要素が親よりも小さい間、親と子を交換することを繰り返せばよい。
次のヒープの*の位置に要素7を追加したとき、Aの位置に来る要素はどれか。
| ア | 7 | イ | 11 | ウ | 24 | エ | 25 |
答え イ
【解説】
*の位置に要素7を追加すると
になる。追加した7と親の節25を比較すると、要素7が小さいので交換する。
次に要素7と親の節11を比較すると、要素7が小さいので交換する。
さらに要素7と親の節9を比較すると、要素7が小さいので交換する。
これで、要素7を追加した処理が完了し、Aの位置に来たのは11(イ)である。
【キーワード】
・ヒープ
- ヒープ(heap)
ヒープ構造とは、2分探索木の一種で、2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さくなるように作られたデータ構造です。
すべてのデータの中で、木の根のデータが最も小さいことが保障されますから、最小値データを取り出すことや、データの追加が最悪でも log(N)時間で行えるという、特徴があります。
ヒープ構図を配列で表現するとき、配列のN番目の要素の子は 2N番目 と 2N+1番目 の要素になります。
もっと、「ヒープ」について調べてみよう。
戻る
一覧へ
次へ