CBMS-2020-10

题目来源：[[做题/文字版题库/CBMS/2020#Question 10|2020#Question 10]] 日期：2024-07-23 题目主题：CS-算法-堆

解题思路

这道题涉及堆（Heap）的构建和堆排序的实现。首先，需要在 $O(n)$ 时间复杂度内构建一个堆；其次，证明堆顶元素为最大值；最后，利用堆进行排序，实现时间复杂度为 $O(n\log n)$ 的排序算法。构建堆的过程需要用到自底向上的堆化操作（heapify），堆排序则通过反复提取最大元素，并调整剩余元素来实现。

Solution

Question 1: Algorithm to Make $H[1,\dots ,n]$ a Heap in $O(n)$ Worst-case Time

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:

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)

Question 2: Proof that $H[1]$ is the Maximum Element if $H[1,\dots ,n]$ is a Heap

Proof:

If $H[1,\dots ,n]$ is a heap, by definition:

$$H\left[\lfloor \frac{i}{2}\rfloor \right]\ge H[i]\text{for}2\le i\le n$$

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

$$H\left[\lfloor \frac{i}{2}\rfloor \right]\ge 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.

Question 3: Algorithm to Sort an Arbitrary Array $H[1,\dots ,n]$ in $O(n\log n)$ Worst-case Time

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:

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.

知识点

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

堆排序 Heap Sort

解题技巧和信息

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