Discussion 9: Heapsort
By this point in the semester, you should be familiar with multiple sorting algorithms, each with its benefits and drawbacks. Insertion sort has great adaptivity and is stable, but has very poor average and worst-case performance. Quicksort is very fast, but is not stable and still has bad worst-case time complexity. Merge sort guarantees better performance bounds, but uses more space and sacrifices adaptivity.
In today’s discussion, we will use the binary heap data structure from lecture to explore the implementation of another sorting algorithm, named heapsort. This sorting algorithm sorts an array with the help of a binary heap, and exhibits a different set of tradeoffs we’ll analyze.
Learning Outcomes
- Translate between the tree and array representations of a heap.
- Implement operations on a heap and determine their time/space complexities.
- Use a heap to implement a priority queue and analyze its performance.
Exercise 1:
Naive Implementation of Heapsort
Heapsort is a sorting algorithm split into two phases. First, all the elements to be sorted are placed into a binary (max) heap. Then, the algorithm repeatedly removes the top element of the heap to recover the final sorted order.
Assume you are given access to a class named
Assume you are given access to a class named
IntegerBinaryMaxHeap, which models a priority queue using a binary max heap and has the following methods:
IntegerBinaryMaxHeap.java
(a)
Using this heap class, write a simple heapsort on an array of integers. Your code should consist of two loops: the first to add every element from the array into the heap, and the second to repeatedly remove from the heap and re-insert the elements back into the array in sorted order.
Remember, the heap provided is a max-heap. Consider what order this means the elements can be removed from this heap.
Heapsort.java
(b)
Draw a loop-invariant diagram for the state of the array
arr for both of the above loops. Include in your invariant what values are currently inside the heap (but it is not necessary to draw a diagram for the heap itself).
(c)
Assuming that the creation of the empty heap can be done in \(O(1)\) time, what is the time complexity of each of your loops relative to the length of the input array \(N\)? What is the overall worst-case runtime complexity of your sorting algorithm?
What is its space complexity?
Exercise 2:
Smarter Implementation of Heapsort
Since a binary heap is implemented using an array, a clever trick involves building the heap directly in the starting array, allowing heapsort to avoid some unnecessary work.
Instead of using the existing heap implementation as a client, you will instead make use of the following helper methods.
(a)
Start by writing a method that takes an array and rearranges its elements to satisfy the invariants of a max-heap.
Hint: Calling
Hint: Calling
bubbleDown() on the root of a subtree will leave the subtree in the correct state as long as all of the children of the subtree's root have already been bubbled down into their correct positions.
(b)
Now, with the array as a max-heap, loop through the array and "remove" from your heap while building up the sorted region of the array. Use the following invariant for your loop:
At each iteration, consider what a standard implementation of
Hint: The body of your loop should make two calls to the helper methods listed above.
Inv:
arr:
0
arr.length
remove() would do to the element at arr[0]. Recall that this is a max-heap. Where does that element end up? What does the invariant require of that resulting location?Hint: The body of your loop should make two calls to the helper methods listed above.
(c)
We can argue that this
What is the space complexity of your
heapify() definition has an \(O(N)\) runtime:
We can bound the total work of
At most \(\frac{N}{2}\) of the entries will begin at level \(\textrm{height} - 1\) in the tree, and they will require at most one swap when they are bubbled down.
Similarly, at most \(\frac{N}{4}\) of the entries will begin at level \(\textrm{height} - 2\) in the tree, and they will require at most two swaps when they are bubbled down.
Continuing this pattern, we find that the total number of swaps can be upper bounded by: \[ \frac{N}{2} + 2 \cdot \frac{N}{4} + 3 \cdot \frac{N}{8} = N \sum_{i=1}^{\infty} \frac{i}{2^i} = 2N = O(N). \]
Including the complexity of heapify() by the total number of swaps that it does during its bubbleDown() calls, as these dominate its runtime.At most \(\frac{N}{2}\) of the entries will begin at level \(\textrm{height} - 1\) in the tree, and they will require at most one swap when they are bubbled down.
Similarly, at most \(\frac{N}{4}\) of the entries will begin at level \(\textrm{height} - 2\) in the tree, and they will require at most two swaps when they are bubbled down.
Continuing this pattern, we find that the total number of swaps can be upper bounded by: \[ \frac{N}{2} + 2 \cdot \frac{N}{4} + 3 \cdot \frac{N}{8} = N \sum_{i=1}^{\infty} \frac{i}{2^i} = 2N = O(N). \]
heapify() you found earlier, what is the total time complexity of your heapsortEff() method? Which of the two steps (heapifying or iterated removing) dominates this complexity?What is the space complexity of your
heapsortEff() method?
Exercise 3:
Running Heapify
Although the code you've written by this point correctly implements heaps and heapsort, it is much more memorable and conceptually
helpful to be able to visualize what heapsort is actually doing, so in this exercise we will trace a full runthrough of the improved heapsort implementation.
Let us suppose that the initial state of the array is:
Let us suppose that the initial state of the array is:
(a)
During three of the iterations of the main loop of
End of iteration: _____________________
End of iteration: _____________________
End of iteration: _____________________
heapify(), the contents of arr are rearrange. Fill in the figures below to visualize the state of arr at the end of these iterations. Label these iterations with the values of any relevant loop variables.End of iteration: _____________________
End of iteration: _____________________
End of iteration: _____________________
(b)
Draw the binary tree representation of the
arr heap at the end of the heapify() method.
(c)
Fill in the state of
arr after the first element has been removed from the heap after the heapify() step of heapsortEff(). What value of i does this correspond to in the loop invariant diagram?
(d)
Draw the binary tree representation of the state of the heap segment of
arr at the point of the execution of part (c).
(e)
Fill in the state of
arr after the first three elements have been removed from the heap after the heapify() step of heapsortEff(). What value of i does this correspond to in the loop invariant diagram?
(f)
Draw the binary tree representation of the state of the heap segment of
arr at the point of the execution of part (e).