Skip to content

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

Author

zephyr

Description

Let \(H[1, \ldots, n]\) be an array of \(n\) real numbers. We call \(H[1, \ldots, n]\) a heap if \(H\left[\left\lfloor \frac{i}{2} \right\rfloor\right] \geq H[i]\) for \(2 \leq i \leq n\), where \(\left\lfloor \frac{i}{2} \right\rfloor\) is the integer quotient of \(i\) divided by 2. Answer the following questions.

(1) Give an algorithm that makes \(H[1, \ldots, n]\) a heap in \(O(n)\) worst-case time.

(2) If \(H[1, \ldots, n]\) is a heap, prove that \(H[1]\) is the maximum element.

(3) Using the notion of heap, describe an algorithm that sorts an arbitrary array \(H[1, \ldots, n]\) in \(O(n \log n)\) worst-case time.

设 \(H[1, \ldots, n]\) 为一个包含 \(n\) 个实数的数组。如果 \(H[1, \ldots, n]\) 满足 \(H\left[\left\lfloor \frac{i}{2} \right\rfloor\right] \geq H[i]\)，其中 \(2 \leq i \leq n\)，且 \(\left\lfloor \frac{i}{2} \right\rfloor\) 为 \(i\) 除以 2 的整数商，则称 \(H[1, \ldots, n]\) 为堆。回答以下问题。

(1) 给出一个使 \(H[1, \ldots, n]\) 在最坏情况下时间复杂度为 \(O(n)\) 的堆化算法。

(2) 如果 \(H[1, \ldots, n]\) 是一个堆，证明 \(H[1]\) 是最大元素。

(3) 使用堆的概念，描述一个在最坏情况下时间复杂度为 \(O(n \log n)\) 的排序任意数组 \(H[1, \ldots, n]\) 的算法。

Kai

(1)

To build a heap in \(O(n)\) time, we can use the "Build-Heap" algorithm which involves calling the "Heapify" function starting from the lowest level of the tree up to the root.

Pseudo-code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
BUILD-HEAP(H)
  n = length(H)
  for i = ⌊n / 2⌋ downto 1
    HEAPIFY(H, i)

HEAPIFY(H, i)
  left = 2 * i
  right = 2 * i + 1
  largest = i

  if left ≤ n and H[left] > H[largest]
    largest = left
  if right ≤ n and H[right] > H[largest]
    largest = right

  if largest ≠ i
    swap H[i] and H[largest]
    HEAPIFY(H, largest)

(2)

Proof:

If \(H[1, \ldots, n]\) is a heap, by definition:

\[ H\left[\left\lfloor \frac{i}{2} \right\rfloor\right] \geq H[i] \quad \text{for} \quad 2 \leq i \leq n \]

For the root element \(H[1]\), consider any element \(H[i]\) in the array. Since \(i \geq 2\), by the heap property, we have:

\[ H\left[\left\lfloor \frac{i}{2} \right\rfloor\right] \geq H[i] \]

By repeatedly applying this property up the tree from any node to the root, it is evident that no descendant of \(H[1]\) can have a value greater than \(H[1]\). Thus, \(H[1]\) is the maximum element in the heap.

(3)

We can use the heap sort algorithm to sort the array. The algorithm involves building a heap from the array and then repeatedly extracting the maximum element from the heap and rebuilding the heap with the remaining elements.

Pseudo-code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
HEAP-SORT(H)
  BUILD-HEAP(H)
  n = length(H)
  for i = n downto 2
    swap H[1] and H[i]
    n = n - 1
    HEAPIFY(H, 1)

BUILD-HEAP(H)
  n = length(H)
  for i = ⌊n / 2⌋ downto 1
    HEAPIFY(H, i)

HEAPIFY(H, i)
  left = 2 * i
  right = 2 * i + 1
  largest = i

  if left ≤ n and H[left] > H[largest]
    largest = left
  if right ≤ n and H[right] > H[largest]
    largest = right

  if largest ≠ i
    swap H[i] and H[largest]
    HEAPIFY(H, largest)

Explanation:

  1. BUILD-HEAP constructs a max-heap from the array in \(O(n)\) time.
  2. HEAPIFY ensures the heap property is maintained.
  3. HEAP-SORT repeatedly extracts the maximum element (root of the heap) and moves it to the end of the array, then reduces the heap size by one and calls HEAPIFY to maintain the heap property. This takes \(O(n \log n)\) time.

Knowledge

堆 堆排序 时间复杂度 算法 排序算法

解题技巧和信息

  1. Build-Heap Time Complexity: The BUILD-HEAP function runs in \(O(n)\) time. Although it appears there are \(n/2\) calls to HEAPIFY, the time complexity analysis shows that the total time is linear due to the nature of heap levels.
  2. Heapify Function: The HEAPIFY function runs in \(O(\log n)\) time since it takes at most the height of the heap to restore the heap property.
  3. Heap Sort: By building the heap in \(O(n)\) time and then performing \(n\) extractions, each taking \(O(\log n)\) time, heap sort achieves an overall time complexity of \(O(n \log n)\).

重点词汇

  • Heap 堆
  • Heapify 堆化
  • Build-Heap 建堆
  • Max-Heap 最大堆
  • Time Complexity 时间复杂度

参考资料

  1. Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. Chap. 6: Heapsort