東京大学 情報理工学系研究科 コンピュータ科学専攻 2017年2月実施 問題3
Author
kainoj, 祭音Myyura
Description
Consider the problem of sorting an array of integers using the heapsort algorithm. Assume that heapsort brings the minimum element to the front.
Answer the following questions.
(1) Heapsort consists of two phases. Explain what is to be performed in each phase.
(2) Consider sorting of the following array using heapsort.
Draw the tree structure of the heap just after the first phase.
(3) Answer the time complexity of each phase when sorting an array of length
(4) Answer the time complexity of obtaining a sorted list of the smallest
(5) The execution time of heapsort on modern computer systems is often longer than that of some other sort algorithms such as quicksort and mergesort when sorting a large array. Explain a possible reason.
Kai
(1)
- Building the heap – level-by-level, starting from the deepest level.
- Extracting minimum
times. Extracting means printing the root value, replacing it with the last heap element, and then fixing heap order. If we represent the heap in an array of length , we can swap first element (minimum) with the last element, fix heap order and call recursively on first elements of array.Resulting array is sorted in descending order. Reverse it for ascending order.
(2)
Let's put elements of
3
/ \
8 1
/ \ / \
5 4 9 7 ] proper heaps
Note that the deepest level consists of
3
/ \
4 1 ]
/ \ / \ ] proper heaps
5 8 9 7 ]
Now we have two proper heaps of height
1
/ \
4 3
/ \ / \
5 8 9 7
(3)
For simplicity, assume that
Phase 1, building the heap is
Now, let's evaluate the right-hand side:
Thus, we can bound the running time as:
See Cormen's Introduction to Algorithms, 3rd ed, Chapter 6.3 for more.
Phase 2 is
Heapsort pseudocode:
heapsort(T[1..n])
build-heap(T[1..n])
for i = n..2
swap(T[1], T[i])
shift-down(T[1..(i-1)], 1)
(4)
(5)
Let's look at an example.
If input array is already sorted, then mergesort will just scan through the array with no swaps.
Same with partition in quicksort.
On the other hand heapsort, after building a heap (
The other reason might be caching.
In heapsort, accessing a parent might result in memory accesses which are distant more than