CMPSC 465 Data Structures & Algorithms
Fall 2021 and Worksheet 3
Monday, September 13, 2021
1. Heap Sort. Please consider the following array
A = [1,2,9,5,6,10].
Suppose we remove the element at position 0 of the heap. How does the resulting heap look? Write
both the array and tree representation of the heap.
Solution:
Our initial tree looks like this:
1
2
5 6
9
10
1. Firstly, we remove the node 1, and replace it with the last node i.e. 10.
10
2
5 6
9
2. Then we run Heapify-Down from the root. That is, we choose the smaller of the children, in
this case between 2 and 9 is 2. This element is now swapped with 10.
2
10
5 6
9
3. Similarly, we choose the smaller number between 5 and 6, then we swap to give us the result.
2
5
10 6
9
2. Heaps. How does the heap looks like after we run Build-heap function on the array
A = [5,3,17,10,84,19,6,22,9]
CMPSC 465, Fall 2021, Worksheet 3 1
.
Our initial tree looks like this:
5
3
10
22 9
84
17
19 6
We run Heapify-Down on this tree, starting from node bn2c−1 down to 0 as follows:
1. Firstly, we swap node 9 and 10.
5
3
9
22 10
84
17
19 6
2. Then we swap 17 and 6.
5
3
9
22 10
84
6
19 17
3. Then we swap 3 and 5.
3
5
9
22 10
84
6
19 17
We got the min-heap, so we do not need to do anything further.
3. Heaps. Show that an n-element binary heap has height blog2 nc.
Solution: Given an n-element heap of height h, we know from Problem 5b in Homework 2 that
2h ≤ n≤ 2h+1−1 < 2h+1. Thus, h≤ log2 n < h+1. Since h is an integer, h = blog2 nc.
4. Creating heaps. We can build a heap by repeatedly inserting the elements into the heap. Would this
always create the same heap as Build-Heap when run on the same input array? Prove that they do, or
provide a counterexample.
CMPSC 465, Fall 2021, Worksheet 3 2
Solution: Consider the array [3,2,1]. If we insert 3, 2 and 1 into the heap in that order, then the
resulting heap array is [1,3,2]. But Build-Heap generates [1,2,3].
5. Find k-th smallest. Given an array of n elements and an integer k ≥ 0 we would like to find the k-th
smallest element in the array.
1. Provide an algorithm for this problem that uses a min heap with running O(n+ k logn).
2. Provide an algorithm for this problem that uses a max heap with running O(n logk).
3. Which algorithm has better running time?
Solution
1. The idea is to construct min heap of size n by calling Build-Heap. Once the min heap is created
we will delete the root of the heap k−1 times. After this, the root node would contain the k-th
smallest element. The running time of Build-Heap is O(n), and removing k−1 elements takes
O(k logn). Hence, the running time is O(n + k log n).
2. The idea is to create max heap and insert the first k elements of the array into the heap. Then,
for each of the remaining elements of the array, if it is smaller than the value of the root node,
we will delete the root of the heap and insert this new element. By the end of the process, we
will only be left with a max heap containing the k smallest elements, and the root node will be
the k-th smallest element. The running time will be O(n logk).
3. The method using min heap can be more efficient for some values of k. When k = O(1) or
k = Θ(n), both methods have the same O running time. However, when k→ ∞ as n→ ∞ and n
is not Θ(n), for example k =
√
n or k = logn, the method using max-heap is more efficient.
CMPSC 465, Fall 2021, Worksheet 3 3