東京大学 新領域創成科学研究科 メディカル情報生命専攻 2014年8月実施 問題9

标签：

• Tokyo-University
• Heap-Sort

Author

zephyr, 祭音Myyura

Description

An array of $n$ real numbers, $H[1, \ldots, n]$, is called a heap if $H[\lfloor i/2 \rfloor] \geq H[i]$ for $1 < i \leq n$, where $\lfloor i/2 \rfloor$ is the quotient of integer $i$ divided by 2 (e.g., $\lfloor 4/2 \rfloor = \lfloor 5/2 \rfloor = 2$). A heap can be treated as a binary tree such that $H[1]$ is the root node and $H[\lfloor i/2 \rfloor]$ is the parent node of $H[i]$. Answer the following questions.

(1) Explain whether array $[6, 3, 4, 1, 0, 3, 4, 2]$ is a heap or not.

(2) Show that if $H[1, \ldots, n]$ is a heap, $H[1, \ldots, j]$ is also a heap for any $j$ $(1 \leq j < n)$.

(3) Suppose that $H[1, \ldots, n]$ is a heap but $H[1, \ldots, n+1]$ is not. Describe a procedure that exchanges elements in $H[1, \ldots, n+1]$ to make it a heap in $O(\log n)$ worst-case time.

(4) Suppose that $H[1, \ldots, n]$ is a heap. Prove that $H[1]$ is maximum among all elements in $H[1, \ldots, n]$. Suppose that after replacing $H[1]$ with $H[n]$, $H[1, \ldots, n-1]$ is not a heap. Describe a procedure that exchanges elements in $H[1, \ldots, n-1]$ to make it a heap in $O(\log n)$ worst-case time.

(5) Describe an algorithm that exchanges elements in $H[1, \ldots, n]$ to make it a heap in $O(n)$ worst-case time.

(6) Using the procedures defined above, describe an algorithm that sorts array $H[1, \ldots, n]$ in $O(n \log n)$ worst-case time.

---

一个包含 $n$ 个实数的数组 $H[1, \ldots, n]$，如果满足 $H[\lfloor i/2 \rfloor] \geq H[i]$ 对于 $1 < i \leq n$，其中 $\lfloor i/2 \rfloor$ 是整数 $i$ 除以 2 的商（例如，$\lfloor 4/2 \rfloor = \lfloor 5/2 \rfloor = 2$），则称其为堆。堆可以被看作是一个二叉树，其中 $H[1]$ 是根节点，$H[\lfloor i/2 \rfloor]$ 是 $H[i]$ 的父节点。回答以下问题。

(1) 解释数组 $[6, 3, 4, 1, 0, 3, 4, 2]$ 是否是一个堆。

(2) 证明如果 $H[1, \ldots, n]$ 是一个堆，那么 $H[1, \ldots, j]$ 也是一个堆，对于任何 $j$ $(1 \leq j < n)$。

(3) 假设 $H[1, \ldots, n]$ 是一个堆，但 $H[1, \ldots, n+1]$ 不是。描述一种在 $O(\log n)$ 最坏情况下，将 $H[1, \ldots, n+1]$ 中的元素交换使其成为堆的方法。

(4) 假设 $H[1, \ldots, n]$ 是一个堆。证明 $H[1]$ 是 $H[1, \ldots, n]$ 中最大的元素。假设在用 $H[n]$ 替换 $H[1]$ 后，$H[1, \ldots, n-1]$ 不是一个堆。描述一种在 $O(\log n)$ 最坏情况下，将 $H[1, \ldots, n-1]$ 中的元素交换使其成为堆的方法。

(5) 描述一种在 $O(n)$ 最坏情况下，将 $H[1, \ldots, n]$ 中的元素交换使其成为堆的算法。

(6) 使用上述定义的方法，描述一种在 $O(n \log n)$ 最坏情况下，对数组 $H[1, \ldots, n]$ 进行排序的算法。

题目描述

对含 $n$ 个实数的数组 $H[1,\ldots,n]$，若

$$H[\lfloor i/2\rfloor]\ge H[i]\qquad(1<i\le n),$$

则称其为堆；这里 $\lfloor i/2\rfloor$ 是 $i$ 除以 $2$ 的整数商。在对应二叉树中，$H[1]$ 为根，$H[\lfloor i/2\rfloor]$ 为 $H[i]$ 的父节点。回答下列问题：

1. 判断数组 $[6,3,4,1,0,3,4,2]$ 是否为堆并说明理由。
2. 证明若 $H[1,\ldots,n]$ 为堆，则任意前缀 $H[1,\ldots,j]$（$1\le j<n$）也为堆。
3. 若 $H[1,\ldots,n]$ 是堆而加入 $H[n+1]$ 后不再是堆，描述仅通过交换元素、在最坏 $O(\log n)$ 时间内恢复 $H[1,\ldots,n+1]$ 堆性质的过程。
4. 证明堆顶 $H[1]$ 是 $H[1,\ldots,n]$ 的最大元素；再设以 $H[n]$ 替换 $H[1]$ 后 $H[1,\ldots,n-1]$ 不再为堆，描述最坏 $O(\log n)$ 时间的交换恢复过程。
5. 描述通过交换元素在最坏 $O(n)$ 时间内把任意 $H[1,\ldots,n]$ 建成堆的算法。
6. 利用上述过程，描述最坏时间为 $O(n\log n)$ 的数组排序算法。

Kai

(1)

To determine if the given array is a heap, we need to check if for every $i > 1$, the condition $H[\lfloor i/2 \rfloor] \geq H[i]$ holds.

• $i = 2$: $\lfloor 2/2 \rfloor = 1 \Rightarrow H[1] = 6 \geq H[2] = 3$
• $i = 3$: $\lfloor 3/2 \rfloor = 1 \Rightarrow H[1] = 6 \geq H[3] = 4$
• $i = 4$: $\lfloor 4/2 \rfloor = 2 \Rightarrow H[2] = 3 \geq H[4] = 1$
• $i = 5$: $\lfloor 5/2 \rfloor = 2 \Rightarrow H[2] = 3 \geq H[5] = 0$
• $i = 6$: $\lfloor 6/2 \rfloor = 3 \Rightarrow H[3] = 4 \geq H[6] = 3$
• $i = 7$: $\lfloor 7/2 \rfloor = 3 \Rightarrow H[3] = 4 \geq H[7] = 4$
• $i = 8$: $\lfloor 8/2 \rfloor = 4 \Rightarrow H[4] = 1 < H[8] = 2$

Since $H[4] = 1$ is not greater than or equal to $H[8] = 2$, the array $[6, 3, 4, 1, 0, 3, 4, 2]$ is not a heap.

(2)

Statement: If $H[1, \ldots, n]$ is a heap, then $H[1, \ldots, j]$ is also a heap for any $j$ $(1 \leq j < n)$.

Proof: Let $H[1, \ldots, n]$ be a heap, meaning $H[\lfloor i/2 \rfloor] \geq H[i]$ for all $1 < i \leq n$. Consider any $j < n$. Since the heap property holds for all elements in $H[1, \ldots, n]$, it will also hold for all elements in $H[1, \ldots, j]$ because the parent-child relationships in the heap are preserved up to index $j$. Therefore, $H[1, \ldots, j]$ is also a heap.

(3)

Suppose $H[1, \ldots, n]$ is a heap, but after inserting an element at position $n+1$, the array $H[1, \ldots, n+1]$ is not a heap. The violation of the heap property could only occur if the newly inserted element at position $n+1$ is greater than its parent. To fix this, we perform the heapify-up operation.

Heapify-up Procedure:

1. Let $i = n+1$.
2. While $i > 1$ and $H[i] > H[\lfloor i/2 \rfloor]$:
   • Swap $H[i]$ and $H[\lfloor i/2 \rfloor]$.
   • Set $i = \lfloor i/2 \rfloor$.

Time Complexity: The worst-case time complexity of this procedure is $O(\log n)$, as we may need to traverse up the height of the heap, which is logarithmic in terms of the number of elements.

(4)

Proof that $H[1]$ is the maximum element in $H[1, \ldots, n]$: By the definition of a max-heap, the root node (i.e., $H[1]$) must be greater than or equal to all its children. By induction, it can be proven that $H[1]$ is greater than or equal to all elements in the heap. Hence, $H[1]$ is the maximum element.

Heapify-down Procedure: After replacing $H[1]$ with $H[n]$, if $H[1, \ldots, n-1]$ is not a heap, we need to restore the heap property by performing the heapify-down operation.

1. Let $i = 1$.
2. While $2i \leq n-1$ (i.e., while $i$ has at least one child):
   • Let $j = 2i$ (left child).
   • If $j < n-1$ and $H[j+1] > H[j]$, set $j = j+1$ (right child is larger).
   • If $H[i] \geq H[j]$, break the loop.
   • Swap $H[i]$ and $H[j]$.
   • Set $i = j$.

Time Complexity: The worst-case time complexity of this procedure is $O(\log n)$, as we may need to traverse down the height of the heap.

(5)

To convert an unordered array $H[1, \ldots, n]$ into a heap, we can use the build-heap algorithm:

Build-Heap Algorithm:

1. Start from the last non-leaf node, $\lfloor n/2 \rfloor$.
2. Perform heapify-down on each node from $\lfloor n/2 \rfloor$ to 1.

Time Complexity: A node of height $h$ costs $O(h)$ to heapify. The number of nodes whose height is at least $h$ is at most $n/2^h$, so the total cost is

$$O\!\left(\sum_{h=1}^{\lfloor\log_2 n\rfloor}\frac{n}{2^h}\right)=O(n),$$

because the geometric series converges.

(6)

Using the above procedures, we can describe the Heapsort algorithm:

1. Build-Heap: Convert the array $H[1, \ldots, n]$ into a max-heap.
2. Extract-Max repeatedly: Swap $H[1]$ with $H[n]$, reduce the size of the heap by 1, and then perform heapify-down on $H[1, \ldots, n-1]$.
3. Repeat the above step until the heap size is reduced to 1.

Time Complexity: The time complexity of Heapsort is $O(n \log n)$ because:

• Building the heap takes $O(n)$ time.
• Each extraction and heapify-down takes $O(\log n)$ time, and there are $n$ such extractions.

Knowledge

堆 堆排序 复杂度分析

解题技巧和信息

堆问题的核心是维护堆的性质，通过理解堆的定义（最大堆或最小堆）来选择合适的操作（如 heapify-up 或 heapify-down）。在建堆和堆排序时，关注堆的高度和操作的时间复杂度。堆操作通常具有 $O(\log n)$ 的时间复杂度，而建堆的复杂度为 $O(n)$。

重点词汇

• heap 堆
• heapify 堆化
• max-heap 最大堆
• build-heap 建堆
• heapify-down 下滤
• heapify-up 上滤

参考资料

1. Introduction to Algorithms, 3rd Edition, Chapter 6: Heapsort
2. Data Structures and Algorithm Analysis in C, Chapter 7: Heaps