Credit: Gavin Taylor for the original version of these notes.

1 Priority Queue ADT

We've finished Maps! It's time for something new. Priority Queues! Priority Queues are a bit like Maps, but instead of every element having a key, it has a priority (usually, these are numbers, but they don't have to be). Once we enter some elements into a PQ, the only element we can pull back out is the one with highest priority. A Maximum Priority Queue consists of the following two methods:

• insert(priority,element): Insert new element with given priority.
• peekMax(): Return (but don't remove) the element with largest priority.
• removeMax(): Return and remove the element with the largest priority.

As you might guess, there is also something called a Minimum Priority Queue, which is exactly the same except it has peekMin() and removeMin() instead. It's easy to find applications of both kinds of priority queues, depending on what you want to do, and everything works exactly the same either way. Just remember that in a Priority Queue you can normally just do one or the other (remove/peek at the min or max, but not both).

Let's look at some dumb ways to do this, first!

Unsorted Array/Linked List: Yeah, we could do this. Insert would be constant time! removeMax(), though, would be O(n), as you'd have to iterate along every element in the PQ to find the maximum, and then remove it.

Sorted Array/Linked List: This maybe feels a little less ugly. Insert now takes O(n), as you have to find the spot for/make room for your new element. removeMax(), though, is now O(1).

Could we do this with binary search trees? I guess we could. I'd rather not, though... it's ugly. All of the removeMax's would require the removal of something from the right side of the tree, causing a large number of rotations. BSTs are designed to make it easy to find anything in the tree, and we don't care about that this time. We just care about finding one particular element, so maybe we can organize things differently in a tree to make this easier? Because different priorities should mean a different structure?

2 Heaps

You would be right! We're going to use something called a Binary Heap (this is usually the type of heap people mean when they just say "heap"). Just as a BST is a type of binary tree with the data organized in a certain way, a Heap is a type of binary tree with the data organized in a different way.

Heaps are really good at being PQs, to the point that using much else would be a little weird. As a result, heaps and Priority Queues are often mixed up by people who haven't learned the difference between an ADT and a data structure. PQ is the ADT. Heap is the data structure.

Heaps have two rules:

1. The priority of a parent is greater than the priority of its children. We know nothing about the comparative priorities of the left and right children. We only know that the parent is of higher priority than the children.
2. The tree is complete. Remember, complete means the tree is as short as possible. Not only will this be complete, but also, if any depth is unfinished, the leaves must be all the way over to the left.

Here's an example of a heap, which follows all the rules above:

3 Fixing a Heap

Imagine you have a heap in every respect, except that just one of the nodes violates the heap order property. How would you fix it?

Fortunately, there is an easy way to fix the heap order property without changing the structure (the completeness property): If the node is bigger than it's parent, swap 'em and keep swapping on up until the parent is bigger than that node. That's called a "bubbble up" operation.

The otheroption is that the node is smaller than one of its children. Then you take whichever child is larger, and swap that with the parent, then keep doing that on down the heap until the node's children are smaller than it is. That's called a "bubble down" operation.

And that's it! We can fix the heap ordering of any single element by either doing a bubble down or a bubble up. And it's pretty easy to see that both of those are going to be \(O(height)\) time operations, which in a heap is always \(O(\log n)\) since heaps are complete. The bubble down and bubble up are what allow you to...

4 Insert

Inserting is pretty simple. Place the new data in the first available spot in the tree (in the above heap, this is the left child of 8). Now, we perform a "bubble up," by running the following loop:

1
2

While the parent is of smaller priority than this data,
  swap the node and its parent.

Let's take the above tree, and add an element with priority 90. We would go through the following steps:

Add the data to the first open slot in the heap.

90>8, so swap.

90>10, so swap.

90<100, so stop.

So an insertion just involves adding to the end of the array, then doing a single bubble up, which is \(O(\log n)\) time.

5 RemoveMax

Doing a peekMax() operation just means returning the root of the tree, so that's going to be \(O(1)\).

However, to remove the max you have to actually change the heap. Insertion involved a bubble-up, so as you might guess removal requires a bubble-down. To do a removeMax(), you take the last element in the tree (in our example, after the insertion of 90, this is 8), and put it as the root. Then,

1
2

While the data is smaller than at least one of the two children,
  Swap with the largest child

Here's the process. First, we put the 8 at the root.

Now, 8 < 90, so perform that swap.

Now, 8 < 9 AND 10, so perform a swap with the larger of the two.

And we're finished!

How long did that take? Again, that took \(O(\log n)\) time.

6 Implementation

This doesn't seem so hard to implement. We just take our familiar TreeNodes, write some methods bubbleUp and bubbleDown, and be done with it! Of course, we'd have to somehow have a pointer to the first available open spot so we could do an insert, and a pointer to the last element, for a removeMax, so maybe it's not easy as all that.

It turns out, though, that when working with a complete tree, it is unnecessary to actually make the TreeNode class and store this as a tree. Instead, we'll use the tree image to help us see what's going on, while actually storing the priority/element pairs in an array. Consider the complete tree below. In this case, the numbers are NOT the data within the nodes; instead, they are the indices of the corresponding array. We keep nothing in index 0 (for convenience), the root in spot 1, its child in index 2, its other child in index 3, and so on. This is convenient, because now if a node is stored in index i, its left child is in 2i, and its right child is in 2i+1. Its parent, due to the magic of integer math, is in i/2.

So for example, given the following heap:

It would be stored in an array as:

[null, 90, 10, 4, 9, 8, 1, 2, 5, 7]

And you can see, for example, that the key 9 is at index 4 in this array. So its parent (10) is at index \(\lfloor\tfrac{4}{2}\rfloor = 2\), its left child (5) is at index \((2\cdot 4=8\), and its right child (7) is at index \((2\cdot 4 + 1 = 9\).

This is what makes heaps awesome and fast! In particular, the fact that we can implement heaps in an array greatly cuts down on their size in memory (since there are no pointers to worry about), and it's the reason why the \(O(\log n)\) of a heap operation is a much "ligher" big-O than the \(O(\log n)\) of an AVL tree operation.

7 Heapify

Now, suppose we have an array full of elements and their priorities, and we want to create a brand new heap, filled with all these elements (note that we don't always have this array ahead of time, so what we're about to talk about won't always be appropriate). How long does this take?

Here's what you might think of doing:

1
2
3
4
5

heapify_first_try(array):
    H = new empty heap
    for each (element, priority) in array:
        H.insert(priority, element)
    return H

Well since each insert() operation is \(O(\log n)\) time, and we do it n times, the total is \(O(n\log n)\).

But wait! Since we are storing the heap in an array, and we start out with an array, we can just do this operation "in place"! What you do is pretend that you have a heap (even though it's totally out of heap-order), then call bubble-up or bubble-down on each element to put it in its proper place. If we do bubble-up's, this looks like:

1
2
3
4
5

heapify_second_try(array):
    H = heap initialized with array (out of order)
    for ii from 1 up to n:
        H.bubbleUp(ii)
    return H

Very cool! This will certainly be a bit faster in practice. But unfortunately, it's still \(O(n\log n)\) time, so not really asymptotically faster than before

But wait! What if we did bubbleDown's instead of bubbleUp's? That would mean starting from the bottom of the heap, but that's fine since we have everything in an array. And this might be faster because most heap elements are "close" to the bottom levels and so don't have very far to go in a bubbleDown operation!

1
2
3
4
5

heapify(array):
    H = heap initialized with array (out of order)
    for ii from n down to 1:
        H.bubbleDown(ii)
    return H

Now if you do our normal worst-case analysis, you multiply the n times through the loop, times \(O(\log n)\) for the worst-case cost of bubbleDown, for \(O(n\log n)\) total again.

But wait! Is that really how much it costs? Think about the last row of the heap. It contains about \(\tfrac{n}{2}\) items, and each one of them has nowhere to go for a bubbleDown. The next row up has about \(\tfrac{n}{4}\) items, each of which has to go down at most 1 level in a bubbleDown. The whole picture looks like this:

Now we have to add up the last column. Time for some math:

Well that infinite series converges to a finite number because of the Cauchy ratio test that you might have learned about in Calculus. In fact, the sum of that infinite series is 2. So the total is \(O(n)\).

HOLY COW! HEAPIFYING IS THE SAME BIG-O AS JUST COPYING THE ARRAY!

Your mind has been blown. This is the first (and only) time in this class where our normal ways of multiplying the cost of the worst-case of each nested loop structure is correct but not tight - meaning this big-O is too big. It's important to know that this can happen sometimes, even if you aren't sure how to do this kind of analysis with summations on your own.

Courtesy xkcd.

8 Heapsort

Suppose we want to put an array of numbers into increasing order (sort them). How would you do it? You would probably come up with something which is O(n^2). Could we use a heap to make this faster?

On the surface, heapsort is very easy: load everything into your heap, then pull it out, one by one. They'll come back out in order. Loading everything in? If we do it bottom-up, it's O(n). Taking everything out? O(n log(n)). So, total runtime O(n log(n)). But, it seemingly requires two arrays!

Consider the following sequence of numbers: 0 2 6 5 3 1 4. We'd like to put these in increasing order. Let's start by heapifying in place. I'll put a | in the array; everything to the right of it has been heapified, everything to the left has not.

We start by putting the last (n+1)/2 things onto the bottom level of the heap; this doesn't require any work: 0 2 6|5 3 1 4. We then put the next (n+1)/4 things on the next level, then fix the two mini-heaps:

• 0|2 6 5 3 1 4
• 0|5 6 2 3 1 4 (2 has bubbled down).

• 0 2 6 5 3 1 4
• 6 5 0 2 3 1 4 (0 has bubbled down once).
• 6 5 4 2 3 1 0 (0 has bubbled down again).

Now, we can do removeMaxs. Here's the first one. Now, the | will mean everything to the right is sorted, and everything to the left is still in the heap.

• 6 5 4 2 3 1 0
• 0 5 4 2 3 1|6 (swapped the last thing with the top thing)
• 5 0 4 2 3 1|6 (0 has bubbled down)
• 5 3 4 2 0 1|6 (0 has bubbled down again)

Do another removeMax, again swapping the top thing for the last thing:

• 5 3 4 2 0 1|6
• 1 3 4 2 0|5 6 (Swap the 1 and the 5)
• 4 3 1 2 0|5 6 (1 has bubbled down)

Again:

• 4 3 1 2 0|5 6
• 0 3 1 2|4 5 6 (swap the 4 and the 0)
• 3 0 1 2|4 5 6 (0 has bubbled down)
• 3 2 1 0|4 5 6 (0 has bubbled down)

Again:

• 3 2 1 0|4 5 6
• 0 2 1|3 4 5 6 (swap the 0 and the 3)
• 2 0 1|3 4 5 6 (0 has bubbled down)

Again:

• 2 0 1|3 4 5 6
• 1 0|2 3 4 5 6 (swap the 1 and the 2)

Again:

• 1 0|2 3 4 5 6
• 0 1 2 3 4 5 6 (swap, and we're sorted)

O(n log(n)), in place! It turns out this is the absolute best we can do in comparison-based sort.

By the way, the typical O(n^2) sort, the algorithm most people come up with on their own, is called bubble sort. Don't use it! Your commander-in-chief would be disappointed.