Prioritizing
We've worked with the priority queue ADT, which allows getting things by some notion of priority. We saw some simple implementations that do one of the main operations (insert/remove) efficiently and the other inefficiently. Today we'll see how to be pretty efficient (log time) on both. What type of data structure do you bet allows this log time?
All the code files for today: MinPriorityQueue.java (interface); ArrayListMinPriorityQueue.java; HeapMinPriorityQueue.java; Heapsort.java; SimpleStudent.java; Roster.java
Heaps
Heaps are based on binary trees. Recall that we call the unique node above a node, say node i, the parent of i. The nodes below node i are the children of i. In a binary tree, every node has 0, 1, or 2 children. The line we draw between two nodes represents an edge.
A heap is an array that we can view as a "nearly complete" binary tree. In other words, we fill in the tree from the root down toward the leaves, level by level, not starting a new level until we have filled the previous level. This is the shape property of a heap. For example, here's a heap and its representation in an array (the same representation works for an arraylist). Each node of the heap has its index in the array appearing above the node, and its contents appear within the node.
It's easy to compute the array index of a node's parent, left child, or right child, given the array index i of the node:
- The parent is at index (i-1)/2 (using integer division).
- The left child is at index 2*i + 1.
- The right child is at index 2*i + 2.
We will always store a heap in an array, but given this simple scheme for determining parent and child indices, it's always easy to interpret the array as a binary tree. If we were going to be excruciatingly accurate, we would always refer to "the node indexed by i," but we will instead use the less cumbersome language "node i."
There are actually two kinds of heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a heap property, the specifics depending on whether we're talking about a max-heap or a min-heap.
In a max-heap, the nodes satisfy the max-heap property:
For every node i other than the root, the value in the parent of node i is greater than or equal to the value in node i.In other words, the value in a node is at most the value in its parent. The largest value in a max-heap must be at the root. A subtree consists of a node and all the nodes below it, either directly or indirectly, and therefore the largest value in a subtree must be at the root of the subtree. The heap in the figure above is a max-heap.
A min-heap is defined in the opposite way, so that the min-heap property is
For every node i other than the root, the value in the parent of node i is less than or equal to the value in node i.In other words, the value in a node is at least the value in its parent. The smallest value in a min-heap must be at the root.
We define the height of a heap to be the number of edges on the longest path from the root down to a leaf. (Recall that a leaf is a node with no children.) The height of a heap with n nodes is Θ(lg n). (More precisely, the height is the greatest integer less than or equal to lg n.) Showing this property is not too hard, and the book does so.
Operations on a heap
We want to allow two operations on a max-heap: insert a new item, and delete the maximum item. In both operations we want to maintain both the shape and heap properties. The trick is for both operations is to fix the shape first, and then to fix the heap property.
Let's consider insert. Suppose we want to insert 15 in the heap shown above. By the shape property, it should go into the position to the right of the value 1, which would be position 10 in the array. (Representing the heap in an ArrayList makes this insertion particularly easy.) So if we put 15 into position 10 the shape property is satisfied.
But what about the heap property? Everything is fine, with the possible exception that the newly inserted item might be bigger than its parent. (It is in our example.) But that is easy to fix — swap the parent and the newly inserted child.
Now we have the same problem, but moved up a level in the heap. Swap keys again:
Now the max-heap property holds everywhere. In general, we keep swapping keys in a node and its parent until the max-heap property is restored. We know that we'll stop eventually, because the highest up that the new key can go is the root.
What about extracting the maximum? Well, we know where the maximum is — it is at the root, position 0 of the array. But simply removing it would leave a hole, which is not allowed.
Also, the heap has one fewer items, so the rightmost leaf at the bottom level has to disappear. We can fix both of these shape problems by moving the rightmost leaf (last item in the occupied portion of the array) to the root (position 0) and decrementing the size of the occupied portion of the array. This is similiar to what we did with an unsorted array implementation last class.
What does this do to the heap property? The left and right subtrees of the root are both valid heaps. But the root's key might be less than the key in one or both of its children. Again, this problem is easy to fix by swapping the root with its larger child. Its larger child will be greater than the original root, everything in its subtree, and the smaller child (and thus everything in the smaller child's subtree). Thus it is the largest key in the heap and should be the new root. But we might have moved the problem down into the subtree, because the value swapped into the subtree's root might violate the heap property of the subtree. In this example, it does:
But this is the same problem, and so we can repeat the operation, swapping the key in a node with the larger of its children until the max-heap property is restored. In our example, one more swap finishes up:
An implementation of a min-heap in an arraylist is in HeapMinPriorityQueue.java. It shows how to implement the operations described above.
Let's look at the worst-case running times of the min-priority queue operations in this implementation. We express them in terms of the number n of elements that will ever be in the min-priority queue at any one time.
- isEmpty just returns a boolean indicating whether the size of the arraylist is zero. This method takes constant time, or O(1).
- insert first adds a new reference at the end of the arraylist, which takes O(1) amortized time. It then has to bubble the value up the heap until it is less than its parent. This takes at most the height of the heap swaps, which takes O(lg n) time.
- The minimum method just has to return what is in position 0 of the arraylist. This takes O(1) time.
- The extractMin method returns the element in position 0 and puts the last element in its place. This takes O(1) time. However, it then has to restore the heap property, so it has to trickle the new root down until it is smaller than both children or is a leaf. This also takes at most the height of the heap swaps, which takes O(lg n) time.
Heapsort
In addition to supporting priority queues, a heap is also the basis of a sorting algorithm called heapsort. Its running time is O(n lg n), and it sorts in place. That is, it needs no additional space for copying things (as mergesort does) or for a stack of recursive calls (quicksort and mergesort). It is a version of selection sort, if you remember that, but instead of running through the entire remaining array to find the next smallest item it uses a heap to organize information.
Heapsort has two major phases. First, given an array of values in an unknown order, we have to rearrange the values to obey the max-heap property. That is, we have to build a heap. Then, once we've built the heap, we repeatedly pick out the maximum value in the heap—which we know is at the root—put it in an appropriate slot in the array (by swapping it with the value in that slot), and restore the max-heap property. Note how convenient this is—the next spot to be filled in selection sort (choosing maximums rather than minimums) goes precisely at the place where the heap has to shrink to maintain the shape property!
The code for heapsort is in Heapsort.java. At the bottom, you can see some private methods that help out other methods in the class: swap, leftChild, and rightChild.
How to build a heap
The obvious way to build a heap is to start with an unordered array. If we just insert one item into the array, then it is a valid heap. We can then insert the second item into the heap and fix up the heap properties, then the third and fix up the heap properties, etc. After we have inserted the last item we have a valid heap. This works fine and leads to an O(n lg n) heapsort. However, we can avoid implementing the insert code and speed up the algorithm a bit by using the code to restore the heap property after a deletion instead. The idea seems a bit strange at first, but it is really quite clever.
The code to restore a heap after a deletion is in maxHeapify method. It takes three parameters: the array a holding the heap and indices i and lastLeaf into the array. The heap is in the subarray a[i..lastLeaf], and when maxHeapify is called, we assume that the max-heap property holds everywhere except possibly among node i and its children. maxHeapify restores the max-heap property everywhere.
maxHeapify works as follows. It computes the indices left and right of the left and right children of node i, if it has such children. Node i has a left child if the index left is no greater than the index lastLeaf of the last leaf in the entire heap, and similarly for the right child.
maxHeapify then determines which node, out of node i and its children, has the largest value, storing the index of this node in the variable largest. First, if there's a left child, then whichever of node i and its left child has the larger value is stored in largest. Then, if there's a right child, whichever of the winner of the previous comparison and the right child has the larger value is stored in largest.
Once largest indexes the node with the largest value among node i and its children, we check to see whether we need to do anything. If largest equals i, then the max-heap property already is satisfied, and we're done. Otherwise, we swap the values in node i and node largest. By swapping, however, we have put a new, smaller value into node largest, which means that the max-heap property might be violated among node largest and its children. We call maxHeapify recursively, with largest taking on the role of i, to correct this possible violation.
Notice that in each recursive call of maxHeapify, the value taken on by i is one level further down in the heap. The total number of recursive calls we can make, therefore, is at most the height of the heap, which is Θ(lg n). Because we might not go all the way down to a leaf (remember that we stop once we find a node that does not violate the max-heap property), the total number of recursive calls of maxHeapify is O(lg n). Each call of maxHeapify takes constant time, not counting the time for the recursive calls. The total time for a call of maxHeapify, therefore, is O(lg n).
Now that we know how to correct a single violation of the max-heap property, we can build the entire heap from the bottom up. Suppose we were to call maxHeapify on each leaf. Nothing would change, because the only way that maxHeapify changes anything is when there's a violation of the max-heap property among a node and its children, but leaves have no children. Now suppose we called maxHeapify on each node that has at least one child that's a leaf. Then afterward, the max-heap property would hold at each of these nodes. But it might not hold at the parents of these nodes. So we can call maxHeapify on the parents of the nodes that we just fixed up, and then on the parents of these nodes, and so on, up to the root.
That's exactly how the buildMaxHeap method works. It computes the index lastNonLeaf of the highest-indexed non-leaf node, and then runs maxHeapify on nodes by decreasing index, all the way up to the root.
You can see how buildMaxHeap works on our example heap, including all the changes made by maxHeapify, by running the slide show in Heapsort.ppt. Run it for 17 transitions, until you see the message "Heap is built."
Let's analyze how long it takes to build a heap. We run maxHeapify on at most half of the nodes, or at most n/2 nodes. We have already established that each call of maxHeapify takes O(lg n) time. The total time to build a heap, therefore, is O(n lg n).
Because we are shooting for a sorting algorithm that takes O(n lg n) time, we can be content with the analysis that says it takes O(n lg n) time to build a heap. It turns out, however, that a more rigorous analysis shows that the total time to run the buildMaxHeap method is only O(n). Notice that most of the calls of maxHeapify made by buildMaxHeap are on nodes close to a leaf. In fact, about half of the nodes are leaves and take no time, a quarter of the nodes are parents of leaves and require at most 1 swap, an eighth of the nodes are parents of the parents of leaves and take at most 2 swaps, and so on. If we sum the total number of swaps it ends up being O(n).
Sorting once the heap has been built
The second phase of sorting is given by the heapsort method in Heapsort.java. After it calls buildMaxHeap so that the array obeys the max-heap property, this method sorts the array. You can see how it works on the example by running the rest of the slide show in Heapsort.ppt.
Let's think about the array once the heap has been built. We know that the largest value is in the root, node 0. And we know that the largest value should go into the position currently occupied by the last leaf in the heap. So we swap these two values, and declare that the last position—where we just put the largest value—is no longer in the heap. That is, the heap occupies the first n-1 slots of the array, not the first n. The local variable lastLeaf indexes the last leaf, so we decrement it. By swapping a different value into the root, we might have caused a violation of the max-heap property at the root. Fortunately, we haven't touched any other nodes, and so we can call maxHeapify on the root to restore the max-heap property.
We now have a heap with n-1 nodes, and the nth slot of the array—a[n-1]—contains the largest element from the original array, and this slot is no longer in the heap. So we can now do the same thing, but now with the last leaf in a[n-2]. Afterward, the second-largest element is in a[n-2], this slot is no longer in the heap, and we have run maxHeapify on the root to restore the max-heap property. We continue on in this way, until the only node that we have not put into the heap is node 0, the root. By then, it must contain the smallest value, and we can just declare that we're done. (This idea is analogous to how we finish up selection sort, putting the n-1 smallest values in the first n-1 slots of the array. We then declare that we are done, since the only remaining value must be the largest, and it's already in its correct place.)
Analyzing this second phase is easy. The while-loop runs n-1 times (once for each node other than node 0). In each iteration, swapping node values and decrementing lastLeaf take constant time. Each call of maxHeapify takes O(lg n) time, for a total of O(n lg n) time. Adding in the O(n lg n) time to build the heap gives a total sorting time of O(n lg n).