平成20年 秋期 基本情報技術者 午前 問12
親の節の値が子の節の値より小さいヒープがある。
このヒープへの挿入は、要素を最後尾に追加し、その要素が親よりも小さい間、親と子を交換することを繰り返せばよい。
次のヒープの＊の位置に要素７を追加したとき、Ａの位置に来る要素はどれか。
ア ７ イ １１ ウ ２４ エ ２５
【キーワード】
・ヒープ
【キーワードの解説】
- ヒープ（heap）
ヒープ構造とは、２分探索木の一種で、２分木の各節点にデータを保持し、親のデータが２つの子のデータよりも小さくなるように作られたデータ構造です。
すべてのデータの中で、木の根のデータがもっとも小さいことが保障されますから、最小値データを取り出すことや、データの追加が最悪でも ｌｏｇ（Ｎ） 時間で行えるという、特徴があります。
ヒープ構図を配列で表現するとき、配列のＮ番目の要素の子は ２Ｎ番目 と ２Ｎ＋１番目 の要素になります。
ヒープ木（ヒープ構造）の操作（データ追加）について問題です。
ヒープ木についてはある程度の知識を持っていても、実際にデータ追加操作をシミュレートしたことのある人は少ないと思いますので、この問題を解いて操作方法について勉強しましょう。
問題にもあるようにデータを追加するときは、最後尾に追加して、親と比較・交換を繰り返すことで行います。それほど難しい内容ではありませんので、問題のヒープにデータをいくつか追加して操作を試してみましょう。できれば、削除処理についても試してみるといいでしょう。
実際にヒープ木をプログラムするときは、扱うデータが構造体になると交換処理の負荷が問題になることがありますので、各要素を参照するポインタ配列を作って、ポインタ配列の交換で行う方法を用いることもあります。
情報処理技術者試験の勉強をやり直しの、平成20年秋期の基本情報技術者、ソフトウェア開発技術者の問題の解説は週に各１０問のペースで追加予定です。（毎週水曜日に公開予定。）
また、キーワード分類のも更新します。
情報処理技術者試験の勉強をやり直しですが、見えないところをいろいろと修正しています。もし、正しく表示されないページがあったら連絡ください。
