東京大学 新領域創成科学研究科 メディカル情報生命専攻 2019年8月実施 問題10
Author
Description
Let
(1) Give an algorithm that makes
(2) If
(3) Using the notion of heap, describe an algorithm that sorts an arbitrary array
设
(1) 给出一个使
(2) 如果
(3) 使用堆的概念,描述一个在最坏情况下时间复杂度为
Kai
(1)
To build a heap in
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)
(2)
Proof:
If
For the root element
By repeatedly applying this property up the tree from any node to the root, it is evident that no descendant of
(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:
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:
- BUILD-HEAP constructs a max-heap from the array in
time. - HEAPIFY ensures the heap property is maintained.
- 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
time.
Knowledge
堆 堆排序 时间复杂度 算法 排序算法
解题技巧和信息
- Build-Heap Time Complexity: The BUILD-HEAP function runs in
time. Although it appears there are calls to HEAPIFY, the time complexity analysis shows that the total time is linear due to the nature of heap levels. - Heapify Function: The HEAPIFY function runs in
time since it takes at most the height of the heap to restore the heap property. - Heap Sort: By building the heap in
time and then performing extractions, each taking time, heap sort achieves an overall time complexity of .
重点词汇
- Heap 堆
- Heapify 堆化
- Build-Heap 建堆
- Max-Heap 最大堆
- Time Complexity 时间复杂度
参考资料
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. Chap. 6: Heapsort