Priority Queue and Heaps

Definitions

Priority Queue

A priority queue behaves like any other queue with one special feature: whenever popping, the highest priority item (think "largest" item) on the queue is the item removed. This implies that the items stored in the queue must be comparable. Like all the other comparison requirements we've seen this semester, this means that operator< must defined for the objects contained in a priority queue.

How might you go about converting the linked-list based queue class that we've seen into a priority queue?

You might be thinking that the problem is easily solved by always storing the items in your queue in sorted order. While this would certainly solve the problem, imagine all the work required to sort the underlying linked-list each time you add (push) an item into the queue.

Consider the worst case scenario: consecutively pushing items of increasing priority without popping. Following each push, you'd have to sort the linked-list so the item bubbled to its place at the top/front, with the data structure getting larger and larger each time, requiring more and more operations each time.

Was all that sorting necessary? No!

Since our requirement was to only get the largest item out of the queue when popping, you could solve this problem by sorting only when popping. This would be a much more efficient solution, but sorting the entire structure is still a lot of work, especially when high priority ("large") items can still be pushed onto the queue.

In our linked-list based queue scenario, our best scenario is probably to find the highest priority ("largest") item in the queue and remove it with each call to pop. This eliminates the need to sort the sort the underlying structure at all, but would still require checking the priority of item in the linked-list to ensure that you're getting the right item.

Heap

A heap is a binary tree with a special set of rules:

1. The items stored in the tree must be comparable with the less-than operator.
2. The item contained by a node is never less than its children.
3. The tree must be a complete binary tree.

Example: Which is a heap?

Answer: The one on the right.

• The left one isn't a complete binary tree.
• In the center one, 52 is less than its child 77.

Using a Heap as a Priority Queue

Based on our defining rules above, a heap becomes a very natural structure with which to implement a priority queue because the highest priority ("largest") item is always at the root of the heap. The challenge becomes how to add and remove items while ensuring that the rules for the heap are not broken.

Adding an Item to Heap

Pseudocode:

1. Get the data into the structure.
• Place the new item into the heap at the first available location to maintain a complete binary tree.
2. Fix the parent-child relationships.
• While the new item has a higher priority than its parent: swap them

The process of the new item rising to its appropriate location in the heap is called reheapification upward.

Example:

Removing an Item from the Heap

Pseudocode:

1. Copy the item at the root of the heap so it can be returned.
2. Copy the last item in the tree into the root and then remove the last node from the tree. This item is referred to as the "out-of-place item".
   (This maintains the tree as complete.)
3. Fix the parent-child relationships.
• While the out-of-place item has a lower priority than either of its children: swap it with the child that has the highest priority
4. Return the copy of the item that was originally at the root.

The process of the out-of-place item falling to its appropriate location in the heap is called reheapification downward.

Example: