配列内に構成されたヒープとして適切なものはどれか。
| ア |  |
| イ |  |
| ウ |  |
| エ |  |
答え イ
【解説】
データの添え字の1の子は2と3、2の子は4と5、3の子は6と7、4の子は8と9、5の子は10と11になります。
選択肢の中からヒープの条件を満足するものを探します。
| ア | 配列の3番目の要素 5 の子の6番目の要素4が、5より小さいのでヒープ構造になっていません。 |
| イ | ヒープ構造です。 |
| ウ | 配列の5番目の要素 8 の子の10番目の要素6が、8より小さいのでヒープ構造になっていません。 |
| エ | 配列の2番目の要素 6 の子の5番目の要素5が、6より小さいのでヒープ構造になっていません。 |
【キーワード】
・ヒープ
- ヒープ(heap)
ヒープ構造とは、2分探索木の一種で、2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さくなるように作られたデータ構造です。
すべてのデータの中で、木の根のデータが最も小さいことが保障されますから、最小値データを取り出すことや、データの追加が最悪でも log(N)時間で行えるという、特徴があります。
ヒープ構図を配列で表現するとき、配列のN番目の要素の子は 2N番目 と 2N+1番目 の要素になります。
もっと、「ヒープ」について調べてみよう。
戻る
一覧へ
次へ