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

标签：

• Kyoto-University
• Max-Heapify
• Heap-Sort
• Algorithm-Complexity
• Binary-Heap

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 の降順に整列された整数列を与えたときの実行時間の漸近的上界をビッグオー記法を用いて答えよ。ただし、オーダーとして最も低いものを答えること。

题目描述

最大堆是近似完全二叉树，每个非根节点值不大于父节点值。用下标从 1 开始的数组表示时，

$$\operatorname{Parent}(i)=\left\lfloor\frac i2\right\rfloor,\quad \operatorname{Left}(i)=2i,\quad \operatorname{Right}(i)=2i+1.$$

1. 在假设 $i$ 的左右子树已为最大堆的条件下，填写题图递归函数 MaxHeapify 的空栏 (1-a)–(1-d)，使以 $i$ 为根的子树变成最大堆。

   

   其中 A.heapsize 是堆中元素数；后问的 A.length 是数组长度，且 A.heapsize ≤ A.length。

2. 对长度 $n$ 的序列，给出 MaxHeapify 最坏运行时间的最低阶大 $O$ 上界。

3. 填写题图 HeapSort 空栏 (3-a)–(3-c)，使用 MaxHeapify 把任意整数序列升序排序；(3-a) 填可能的最小值。

   

4. 求该算法对长度 $n$ 的未排序整数序列的最坏运行时间最低阶上界。

5. 求输入已按降序排列时的运行时间最低阶上界。

考点

• 二叉最大堆与 MaxHeapify：比较父节点和两个孩子，交换最大者后递归恢复堆性质。
• 堆排序构建与抽取：自底向上建堆，再反复交换堆顶、缩小堆并下沉。
• 复杂度分析：分析堆高得到单次 $O(\log n)$，整体对任意输入（包括降序）为 $O(n\log 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)$