京都大学 情報学研究科 知能情報学専攻 2023年8月実施 情報学基礎 F2-1

Author

祭音Myyura

Description

設問 max ヒープは根以外のノードの値が必ず親クードの値の大きさ以下になっている、おおよそ完全二分木である。 max ヒープはインデックスが 1 から始まる配列として表現でき、インデックス i のノードの親ノード、左の子ノード、右の子ノードのインデックスはそれぞれ、Parent(i)=\(\lfloor \frac{\text{i}}{2} \rfloor\)、Left(i) = 2i、Right(i) = 2i+1 として求められる。 ただし、\(\lfloor \cdot \rfloor\) は床関数である。

(1) インデックス \(i\) のノードを根とする部分木が max ヒープとなるように変換する再帰的関数 MaxHeapify を表す次の疑似コードをそれぞれの四角 ((1-a)、(1-b)、(1-c)、(1-d)) を埋めることにより完成させよ。この疑似コードでは、インデックス \(i\) の左の子ノードと右の子ノードを根とする部分木はともに max ヒープであると仮定する。

ただし、A.heapsize は配列 A に格納されているヒープを構成する要素の数を表す。(3) で用いる A.length は配列 A そのものの大きさを表し、A.heapsize \(\le\) A.length である。

(2) (1) の MaxHeapify に長さ n の整数列を与えたときの最悪実行時間の漸近的上界をビッグオー記法を用いて答えよ。ただし、オーダーとして最も低いものを答えること。

(3) (1) の MaxHeapify を用いて任意の整数列を昇順にソートするアルゴリズム HeapSort を表す次の疑似コードをそれぞれの四角 ((3-a)、(3-b)、(3-c)) を埋めることにより完成させよ。ただし、(3-a) には考えうる最も小さい値を入れること。

(4) (3) のアルゴリズムに長さ n の整列されていない整数列を与えをたときの最悪実行時間の漸近的上界をビッグオー記法を用いて答えよ。ただし、オーダーとして最も低いものを答えること。

(5) (3) のアルゴリズムに長さ n の降順に整列された整数列を与えたときの実行時間の漸近的上界をビッグオー記法を用いて答えよ。ただし、オーダーとして最も低いものを答えること。

Kai

(1)

• (1-a): A[lft] > A[largest]
• (1-b): A[rgt] > A[largest]
• (1-c): largest != i
• (1-d): MaxHeapify(A, largest)

(2)

\(O(\log n)\)

(3)

• (3-a): \(\lfloor \frac{\text{A.heapsize}}{2} \rfloor\)
• (3-b): MaxHeapify(A, i)
• (3-c): MaxHeapify(A, 1)

(4)

\(O(n \log n)\)

(5)

\(O(n \log n)\)