2008年(平成20年) 秋期 基本情報技術者 午前 問12

親の節の値が子の節の値より小さいヒープがある。
このヒープへの挿入は、要素を最後尾に追加し、その要素が親よりも小さい間、親と子を交換することを繰り返せばよい。
次のヒープの*の位置に要素7を追加したとき、Aの位置に来る要素はどれか。

【キーワード】
・ヒープ

• ヒープ(heap)
  ヒープ構造とは、2分探索木の一種で、2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さくなるように作られたデータ構造です。
  すべてのデータの中で、木の根のデータが最も小さいことが保障されますから、最小値データを取り出すことや、データの追加が最悪でも log(N)時間で行えるという、特徴があります。
  ヒープ構図を配列で表現するとき、配列のN番目の要素の子は 2N番目 と 2N+1番目 の要素になります。

戻る 一覧へ 次へ