今週の午後問題〔解答〕アルゴリズム ヒープの性質を利用したデータの整列 2018 年度 春期

このコーナーでは毎週月曜に午後の必須選択問題から 1 問ピックアップして出題し、 解答欄 を設け、読者の皆さまにも解答してもらっています！

今週の午後問題は「ヒープの性質を利用したデータの整列」でしたが、皆さん、手応えはいかがでしょうか?

金曜になりましたので、出題の 解答 と 矢沢久雄さんによる 解説 に加えて、皆さんの正解率を公開します。

設問 1a

正解 イ

heap の末端に追加されたデータは、そのデータが親より大きい限り、データと親を交換することを繰り返します。

したがって、空欄 a は、「データ ＞ 親」を意味する heap[k] > heap[parent(k)] が適切です。

設問 1b

正解 エ

heap[k] と heap[parent(k)] の値を交換するので、 swap(heap, h, parent(k)) が適切です。

空欄 b には、 parent(k) が入ります。

設問 2c

正解 エ

1 回目の処理では、 last = 6 であり副プログラム swap によって、 heap[0] の 60 と、 heap[6] の 20 が交換されます。

したがって、 heap[0] の値は、 20 になります。

設問 2d

正解 イ

この部分の説明は、副プログラム downHeap の 7 行目の

heap[tmp] ≦ heap[rchild(n)]

に該当します。 5 行目で tmp に lchild(n) を代入しているので、 7 行目は

heap[lchild(n)] ≦ heap[rchild(n)]

と同じです。

したがって、

右側の子が左側の子以上のときには

という条件になります。

設問 2e

正解 イ

1 回目の処理では、 heap[0] の左側の子が heap[1] = 30 で、右側の子が heap[2] = 45 です。

| ▲ heap[tmp] > heap[n]
| | ･ swap (heap, n, tmp)
| +---
| | ･ return                /* downHeap から抜ける */
| ▼
| ･ n ← tmp

これは、

右側の子が左側の子以上のときには

という条件に一致するので、 15 行目では tmp に右側の子の要素番号の 2 が格納されています。