CBMS-2015-09

题目来源：Question 9 日期：2024-08-01 题目主题：CS-算法-堆和排序

Solution

Question 1: Verify if the array $[6,3,4,1,0,3,4,2]$ is a heap

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 ]\ge H[i]$ holds.

• $i=2$: $\lfloor 2/2\rfloor =1\Rightarrow H[1]=6\ge H[2]=3$
• $i=3$: $\lfloor 3/2\rfloor =1\Rightarrow H[1]=6\ge H[3]=4$
• $i=4$: $\lfloor 4/2\rfloor =2\Rightarrow H[2]=3\ge H[4]=1$
• $i=5$: $\lfloor 5/2\rfloor =2\Rightarrow H[2]=3\ge H[5]=0$
• $i=6$: $\lfloor 6/2\rfloor =3\Rightarrow H[3]=4\ge H[6]=3$
• $i=7$: $\lfloor 7/2\rfloor =3\Rightarrow H[3]=4\ge 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.

Question 2: Subheap Property

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

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

Question 3: Fixing the Heap Property after Insertion

Suppose $H[1,\dots ,n]$ is a heap, but after inserting an element at position $n+1$, the array $H[1,\dots ,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.

Question 4: Extract-Max and Heapify-down

Proof that $H[1]$ is the maximum element in $H[1,\dots ,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,\dots ,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\le 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]\ge 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.

Question 5: Build Heap from Unordered Array

To convert an unordered array $H[1,\dots ,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.

Question 6: Heapsort Algorithm

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

1. Build-Heap: Convert the array $H[1,\dots ,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,\dots ,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.

知识点

堆堆排序复杂度分析

解题技巧和信息

堆问题的核心是维护堆的性质，通过理解堆的定义（最大堆或最小堆）来选择合适的操作（如 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