We have worked with min-heaps, which are sensible for priority queues. But now we need to use max-heaps, which have the same structural requirements as min-heaps, but have the following ordering requirement.
(Ordering requirement for max-heaps) The priority in a node must be no smaller than the priority in each of that node's children (if it has any children).
In a max-heap, the largest value is at the root.
To use heaps for priority queues, it is sensible to store an (item, priority) pair at each node. But for this page, let's get rid of the item entirely and only store the priority. The array is just an array of integers.
That requires some modifications to reheapUp and reheapDown, but those are easy to do. Let's call the new functions reheapUpMax and reheapDownMax.
Suppose that A is an array of n integers, in an arbitrary order. We would like to reorder it to make it into a heap.
It suffices to work from the bottom of the heap to the top. At each step, we do a reheapDownMax step to push a value down into the two max-heaps below it. (They will be max-heaps because the process works from the bottom to the top.) After the reheapDownMax step at a given node, that node will be the root of a max-heap.
There is no need to do anything at leaves, since the values in leaves cannot move any lower in the heap. So we can start at the parent of the last node in the heap, which is the node with the largest index that has at least one child.
Here is an implementation of buildHeap based on those ideas.
// buildHeap(A,n) reorders A[0,...,n-1] so that it
// statisfies the ordering requirement of a max-heap.
void buildHeap(int A[], int n)
{
for(int i = parent(n-1); i >= 0; i--)
{
reheapDownMax(i, A, n);
}
}
To sort an array of size n, our goal is to maintain a loop invariant: keep the array in a state where the first k members are a max-heap and the last n − k members are in the correct position for sorted order.
----------------
| |
| a max-heap | k values
| |
|----------------|
| |
| finished | n - k values
| |
----------------
That is easy to get started by calling buildHeap and setting k = n.
Then the entire array is a max-heap and none of the values are in correct position.
Notice that the largest value in the max-heap is at its root, which is at index 0 in the array. If we swap that value with the last position (index k−1) in the max-heap, then that value is in the correct position.
Now the finished part is one larger and the heap is one smaller. But the heap is not ordered correctly, since the new value at index 0 (the root of the heap) is too small. So we call reheapDownMax to push it down into the now-smaller max-heap. Here is the algorithm to sort an array.
// heapSort(A, n) sorts A[0,...,n-1] into nondescending order.
void heapSort(int A, int n)
{
buildHeap(A, n);
k = n;
while(k > 1)
{
swap(A[0], A[k-1]);
k--;
reheapDownMax(0, A, k);
}
}
When there is just one value left in the max-heap, it must be
the smallest value in the array, and the sort is finished.
Let's look at how long it takes to run heapSort on an array of size n, in the worst case.
The loop performs reheapDownMax a total of n−1 times. Although the heap keeps getting smaller and smaller, imagine that its size is always n; that will only cause us to overcount the total cost.
It takes time O(log2(n)) to perform a reheapDownMax call on a heap with n things in it. Since with do fewer than n calls to reheapDownMax, the total time for the loop is O(nlog2(n)).
It is easy to see that we have not overcounted by much. Half of the reheapDownMax calls are done on heaps of size at least n/2. Their cost is about log2(n/2) = log2(n) − 1. So the first n/2 iterations of the loop take time about (n/2)(log2(n) − 1), which is Ω(nlog2(n)). So the total worst-case time for the loop is Θ(nlog2(n)).
That only leaves the buildHeap step. For simplicity, look at a heap where every level is full, and count the number of swaps that are done by buildHeap. About half of the nodes are in the bottom level, and they cost nothing. About a 1/4 of the nodes are in the next level up from the bottom, and they only cost 1 because there is only one level below them. About 1/8 of the nodes are at the next level up, and they cost no more than 2, since that is as far as they can move down. The total cost is 0(n/2) + 1(n/4) + 2(n/8) + 3(n/16) + … = n(1/4 + 2/8 + 3/16 + 4/32 + ...). The sum (1/4 + 2/8 + 3/16 + 4/32 + ...) can be shown to be less than 1. (If you carry it out to infinity, it is exactly 1.) So the time required to do the buildHeap call is O(n).
Modify the definitions of reheapUp and reheapDown on the previous page to get the definitions of reheapUpMax and reheapDownMax. Keep in mind that the array is now an array of integers, not an array of ItemAndPriority structures. Answer
Simulate buildHeap on the following array. Show both the array and the heap (as a tree) at the beginning and after each iteration of the loop.
---------
| 5 |
|---------|
| 2 |
|---------|
| 80 |
|---------|
| 10 |
|---------|
| 50 |
|---------|
| 9 |
---------
Answer
Simulate heapSort on the following array. It is already a heap, so skip the buildHeap step. Just simulate the loop. Show the array and the heap (as a tree) at the beginning and after each iteration of the loop.
---------
| 80 |
|---------|
| 50 |
|---------|
| 9 |
|---------|
| 10 |
|---------|
| 2 |
|---------|
| 5 |
---------
Answer
An alternative way to perform buildHeap is to keep the array in the following form.
----------------
| |
| a max-heap | k values
| |
|----------------|
| |
| not looked at | n - k values
| |
----------------
The max-heap part can be enlarged by one by
inserting the first value in the unlooked-at part
into the max-heap. That is just a matter of doing
a reheapUpMax step starting at index k, then
adding 1 to k because the heap is one larger.
Write an implementation of this version of buildHeap.
Answer
Using big-O notation, analyze how much the implementation of buildHeap in the previous question takes, as a function of n, in the worst case. Answer
The following algorithm sorts an array. Procedure swap(x,y) swaps the contents of variables x and y.
// insert(A,n) sorts A[0,...,n-1] into nondescending order.
//
// Requirement: A[0,...,n-2] is already in nondescending order.
void insert(int A[], int n)
{
int k = n-1;
while(k > 0 && A[k] < A[k-1])
{
swap(A[k], A[k-1]);
k--;
}
}
// sort(A,n) sorts A[0,...,n-1] into nondescending order.
void sort(int A[], int n)
{
for(int k = 2; k <= n; k++)
{
insert(A, k);
}
}
How much time does it take to do insert(A,n), in the worst case? Use big-Θ notation, and express your answer as a function of n.
How much time does it take to do sort(A,n), in the worst case? Use big-Θ notation, and express your answer as a function of n.
How does this sorting algorithm compare with heapSort in terms of its time requirement?