基本情報技術者 2018年 春期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
ヒープの性質を利用して、データを昇順に整列するアルゴリズムを考える。ヒープは二分木であり、本問では、親は一つ又は二つの子をもち、親の値は子の値よりも常に大きいか等しいという性質をもつものとする。ヒープの例を図1に示す。図1において、丸は節を、丸の中の数値は各節が保持する値を表す。子をもつ節を、その子に対する親と呼ぶ。親をもたない節を根と呼び、根は最大の値をもつ。
〔プログラム1の説明〕
(1) 配列の要素番号は、0から始まる。
(2) 副プログラムmakeHeapは、整数型の1次元配列dataに格納されているhnum個（hnum > 0）のデータを、次の①〜③の規則で整数型の1次元配列heapに格納して、ヒープを配列で実現する。この状態を、“配列heapは、ヒープの性質を満たしている”という。
① 配列要素heap[i]（i = 0, 1, 2, …）は、節に対応する。配列要素heap[i]には、節が保持する値を格納する。
② 配列要素heap[0]は、根に対応する。
③ 配列要素heap[i]（i = 0, 1, 2, …）に対応する節の左側の子は配列要素heap[2×i+1]に対応し、右側の子は配列要素heap[2×i+2]に対応する。子が一つの場合、左側の子として扱う。
(3) 図1のヒープの例に対応した配列heapの内容を、図2に示す。
(4) 親の要素番号と子の要素番号を関係付ける三つの関数がある。
① 整数型：lchild(整数型：i)
要素番号iの配列要素に対応する節の左側の子の配列要素の要素番号2×i+1を計算して返却する。
② 整数型：rchild(整数型：i)
要素番号iの配列要素に対応する節の右側の子の配列要素の要素番号2×i+2を計算して返却する。
③ 整数型：parent(整数型：i)
要素番号iの配列要素に対応する節の親の配列要素の要素番号(i−1)÷2（小数点以下切捨て）を計算して返却する。
(5) 副プログラムswapは、二つの配列要素に格納されている値を交換する。
(6) 副プログラムmakeHeapの引数の仕様を表1に、副プログラムswapの引数の仕様を表2に示す。
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：heap[k] > heap[lchild(k)]
イ：heap[k] > heap[parent(k)]
ウ：heap[k] > heap[rchild(k)]
エ：heap[k] < heap[lchild(k)]
オ：heap[k] < heap[parent(k)]
カ：heap[k] < heap[rchild(k)]
bに関する解答群
ア：heap[hnum-1]
イ：heap[k]
ウ：parent(hnum-1)
エ：parent(k)
模範解答
a：イ、b：エ
解説
解答の導き方
配列に追加した値が、ヒープの性質を保っているかを確かめる問題です。ヒープでは、問題文にあるとおり「親の値は子の値よりも常に大きいか等しい」必要があります。
-
a では、追加した値とその親の値を比べます。
k は、追加したデータが入っている要素番号です。親の要素番号は parent(k) なので、親子の値を比べる式は heap[k] と heap[parent(k)] です。子の値が親より大きいと、ヒープの性質に反します。そのため、交換が必要な場合を表す条件はです。したがって、a は イ です。 -
b には、交換相手の要素番号を指定します。
swap は、二つの要素番号にある値を入れ替える副プログラムです。交換するのは、現在の要素 k と、その親の要素 parent(k) です。したがって、swap に渡すもう一方の要素番号は parent(k) となり、b は エ です。図2では、要素番号4の親は要素番号1です。実際に、parent(4) = (4−1)÷2 = 1 となります。このように、parent(k) で親の要素番号を求められます。
誤りやすいポイント
-
値の比較方向を逆にしないようにします。
この問題では親の値が子の値以上である必要があります。子の値が親の値より大きい場合に交換するため、条件は heap[k] > heap[parent(k)] です。 -
親と比べるのか、子と比べるのかを確認します。
今回は追加した要素を親と比べます。lchild(k) と rchild(k) は子の要素番号を求める関数なので、a の比較相手にはなりません。 -
交換する値ではなく、要素番号を指定します。
swap に渡すのは交換したい値ではなく、その値が入っている場所です。交換する場所は k と parent(k) です。
FAQ
Q: heap[k] が親の値より大きい場合、なぜ交換するのですか？
A: 親の値は子の値以上でなければならないからです。子の値が親より大きい場合は、親子の値を交換して、ヒープの性質に合うようにします。
A: 親の値は子の値以上でなければならないからです。子の値が親より大きい場合は、親子の値を交換して、ヒープの性質に合うようにします。
Q: parent(k) は何を返しますか？
A: 要素番号 k に対応する節の親の要素番号を返します。問題文では、親の要素番号を (i−1)÷2（小数点以下切捨て）で求めると説明されています。
A: 要素番号 k に対応する節の親の要素番号を返します。問題文では、親の要素番号を (i−1)÷2（小数点以下切捨て）で求めると説明されています。
Q: swap に heap[k] を渡さないのはなぜですか？
A: swap は、配列のどの二つの位置にある値を交換するかを要素番号で受け取るためです。値そのものではなく、要素番号を渡します。
A: swap は、配列のどの二つの位置にある値を交換するかを要素番号で受け取るためです。値そのものではなく、要素番号を渡します。
関連キーワード: ヒープ、二分木、配列、ヒープソート
設問2：
問題文を見る〔プログラム2の動作〕の記述中のに入れる正しい答えを、解答群の中から選べ。
〔プログラム2の説明〕
(1) 副プログラムheapSortは、最初に副プログラムmakeHeapを使って、配列heapにデータを格納する。配列heapは、整列対象領域と整列済みデータ領域に分かれている（図3参照）。lastは、整列対象領域の最後の配列要素の要素番号を示している。最初は、配列heap全体が整列対象領域であり、このときlastの値はhnum−1である。
(2) 整列対象領域がヒープの性質を満たすとき、配列要素heap[0]の値は、この領域での最大の値となっている。そこで、配列要素heap[0]の値と配列要素heap[last]の値を交換し、lastの値を1減らして、整列対象領域の範囲を狭め、整列済みデータ領域を広げる。値の交換によって、整列対象領域はヒープの性質を満たさなくなるので、副プログラムdownHeapを使って、整列対象領域のデータがヒープの性質を満たすように再構成する。これを繰り返すことによって、整列済みデータ領域には昇順に整列されたデータが格納されることになる。
(3) 副プログラムheapSortの引数の仕様を表3に、副プログラムheapSortで使用する副プログラムdownHeapの引数の仕様を表4に示す。
〔プログラム2の動作〕
副プログラムheapSortの行番号3の実行が終了した直後のαにおける配列heapの内容は、図2のとおりであった。このとき、副プログラムheapSortの行番号4から行番号7までの1回目の繰返し処理について考える。
副プログラムheapSortの行番号5の副プログラムswapの実行が終了した直後の配列要素heap[0]の値は、cとなる。このため、配列heapの要素番号0からhnum−2までのデータは、根に対応する配列要素heap[0]が最大の値をもつというヒープの性質を満たさなくなる。
副プログラムheapSortの行番号6で呼び出している副プログラムdownHeapは、配列heapの整列対象領域の要素番号0からhlastまでのデータがヒープの性質を満たすように、その領域のデータを次の手順で再構成する。
(1) 配列要素の値の大きさを比較する際に使用する要素番号をnとし、nの初期値を0とする。
(2) 要素番号nの配列要素に対応する節の左側の子の要素番号をtmpに代入する。要素番号nの子が二つあり（rchild(n) ≦ hlast）、右側の子の値が左側の子の値d、右側の子の要素番号をtmpに代入する。
(3) 子に対応する配列要素heap[tmp]の値と、その親に対応する配列要素heap[n]の値とを比較し、配列要素heap[tmp]の値が大きければ、配列要素heap[n]の値と配列要素heap[tmp]の値を交換し、tmpを次のnとして(2)に戻る。ここで、副プログラムdownHeapの行番号15において最初にnに代入するtmpの値は、eである。
cに関する解答群
ア：5
イ：10
ウ：15
エ：20
dに関する解答群
ア：以下のときには
イ：以上のときには
ウ：よりも大きいときには
エ：よりも小さいときには
eに関する解答群
ア：1
イ：2
ウ：3
エ：4
オ：5
カ：6
模範解答
c：エ、d：イ、e：イ
解説
解答の導き方
この問題では、最初に最大の値を根に置くヒープを作り、その根の値を配列の末尾へ移します。その後、残った部分をもう一度ヒープの性質に合うように整えます。ヒープとは、「親の値が子の値以上」という決まりをもつ木構造です。
c：交換直後のheap[0]
図2の配列は、要素番号0から順に次の値です。
最初の繰返しでは、lastは配列の最後の要素番号である6です。プログラム2の行番号5では、heap[0]とheap[last]、つまりheap[0]とheap[6]を交換します。
- 交換前：heap[0]は60、heap[6]は20
- 交換後：heap[0]は20、heap[6]は60
したがって、交換直後のheap[0]の値は20です。これがcに入ります。最大の値60は配列の末尾に移り、以降の整列対象領域から外れます。
d：右側の子を選ぶ条件
プログラム2では、downHeapにheapとlast−1を渡しています。最初のlastは6なので、整列対象領域は要素番号0から5までです。要素番号6は整列済みデータ領域に入ったため、比較の対象にはしません。
downHeapの最初のnは0です。要素番号0の子は、左が1、右が2です。交換後の値はheap[1]が30、heap[2]が45です。
ヒープでは、親より大きい子があれば、その子と親を交換します。そこで、子のうち大きいほうを選ぶ必要があります。プログラムでは、まず左側の子の値をtmpで指し、右側の子が存在するときに、右側の値が左側の値以上ならtmpを右側の要素番号に変更します。
つまり、右側の子の値が左側の子の値「以上のときには」、右側の子を選びます。30と45を比べると45のほうが大きいので、tmpは右側の子の要素番号2になります。これがdです。
e：最初にnに代入するtmp
ここで、heap[tmp]はheap[2]の45、heap[n]はheap[0]の20です。子の値45のほうが親の値20より大きいので、プログラムはこの二つの値を交換します。
続いて、行番号15でnにtmpを代入します。このときtmpは要素番号2なので、最初にnに代入される値も2です。これがeです。
ここで代入するのは値45ではなく、配列の要素番号2です。downHeapは、交換した子の位置からさらに下へ進み、ヒープの性質が保たれているかを確認します。
誤りやすいポイント
-
交換後もheap[0]を最大の値だと思う
heap[0]とheap[6]を交換した直後は、heap[0]は20です。交換によって根の値が変わるため、ヒープの性質が崩れることがあります。 -
整列済みの要素まで比較する
交換後、最大の値60は要素番号6に置かれます。downHeapの対象は要素番号0から5までなので、要素番号6は含めません。 -
子のうち小さいほうを選ぶ
親より大きい子と交換して、親を大きい値にする必要があります。そのため、子が二つあるときは大きいほうを選びます。 -
eを値と取り違える
nやtmpに入るのは値ではなく要素番号です。今回、交換する値は20と45ですが、nに代入されるのは45ではなく要素番号2です。
FAQ
Q: なぜheap[0]と末尾の値を交換するのですか？
A: ヒープでは根が最大の値です。その最大値を配列の末尾に移せば、そこを整列済みの位置にできます。残りの領域について同じ処理を繰り返すと、最大値が右端から順に並び、全体が昇順になります。
A: ヒープでは根が最大の値です。その最大値を配列の末尾に移せば、そこを整列済みの位置にできます。残りの領域について同じ処理を繰り返すと、最大値が右端から順に並び、全体が昇順になります。
Q: 右側の子と左側の子が同じ値でも、右側を選ぶのですか？
A: はい。このプログラムは、右側の値が左側の値以上なら右側を選びます。「以上」には、同じ値の場合も含まれます。
A: はい。このプログラムは、右側の値が左側の値以上なら右側を選びます。「以上」には、同じ値の場合も含まれます。
Q: downHeapで交換した後、なぜnを更新するのですか？
A: 交換した場所の下で、さらにヒープの性質が崩れている可能性があるためです。交換先の子の位置を次のnにして、そこから下の子と比べ直します。
A: 交換した場所の下で、さらにヒープの性質が崩れている可能性があるためです。交換先の子の位置を次のnにして、そこから下の子と比べ直します。
関連キーワード: ヒープソート、最大ヒープ、二分木、配列、ヒープの再構成
