京都大学 情報学研究科 知能情報学専攻 2023年8月実施 情報学基礎 F2-1
Author
祭音Myyura
Description
設問 max ヒープは根以外のノードの値が必ず親クードの値の大きさ以下になっている、おおよそ完全二分木である。
max ヒープはインデックスが 1 から始まる配列として表現でき、インデックス i のノードの親ノード、左の子ノード、右の子ノードのインデックスはそれぞれ、Parent(i)=
(1) インデックス

ただし、A.heapsize は配列 A に格納されているヒープを構成する要素の数を表す。(3) で用いる A.length は配列 A そのものの大きさを表し、A.heapsize
(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)
(3)
- (3-a):
- (3-b): MaxHeapify(A, i)
- (3-c): MaxHeapify(A, 1)