Skip to content

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

Author

zephyr

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]\) 进行排序的算法。

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):
  3. Let \(j = 2i\) (left child).
  4. If \(j < n-1\) and \(H[j+1] > H[j]\), set \(j = j+1\) (right child is larger).
  5. If \(H[i] \geq H[j]\), break the loop.
  6. Swap \(H[i]\) and \(H[j]\).
  7. 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: The build-heap process has a time complexity of \(O(n)\), as it performs a linear number of operations over the array.

(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