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).
• 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? Different priorities should mean a different structure.

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:

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

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

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.

The root in spot 0, its child in index 1 and 2, their children are in 3, 4, 5, and 6, and so on. This is convenient, because now if a node is stored in index \(i\), its left child is in \(2i+1\) and its right child is in \(2i+2\), and its right child is in \(2i+1\). Its parent, due to the magic of integer math, is in \((i-1)/2\).

So for example, given the following heap:

It would be stored in an array as:

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

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

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.

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

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

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

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²). 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)

We then heapify the next (n+1)/8 things:

• 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:</p>

• 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²) 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.