Priority Queues: Sorting's unsung hero, and the true champion of Graph Algorithms

mgcadmin 03-03-2022

Exploring binary heaps for efficiently implementing the Priority Queue ADT.

The Priority Queue ADT

Unlike a regular queue which operates on a first-in first-out fashion, or the Last-in First-out ordering of a stack, a priority queue removes elements based on a associated weight, or priority - hence the name. Priority Queues underpin an enormous number of operations from sorting algorithms (selection sort, heap sort) to graphing algorithms (Dijkstras algorithm, Prims minimum spanning tree algorithm), even job scheduling for operating system kernels, the list goes on and on. Clearly, priority queues are an important data structure.

Priority Queues are a purely abstract data structure with a vast number of possible implementations for the underlying operations. Everything from unordered arrays, to sorted linked lists, to self balancing binary search trees and everything in between can be used to implement the priority queue ADT, all of which with there own advantages and disadvantages.

One of the most popular choices for implementing a priority queue is the binary heap, which is the implementation i will discuss in this article.

Fundamental Priority Queue Operations

Regardless of the implementation choice, priority queues MUST support the following operations:

• insert() - add an item to the priority queue
• getPriority() - remove the item with highest (or lowest) priority
• peek() - get the value of the item with highest (or lowest) priority without removing it
• isEmpty() - check is any items in the queue
• size() - the number of items in the queue

And sometime, but not strictly:

• changePriority() - change the priority of an item in the queue
• merge() - merge two priority queues into one

As mentioned above, depending on the underlying data structure used to implement the priority queue ADT these operations can have varying complexity, as displayed by the following table:

 

Name	Insert	Peek	Remove
Unordered Array	O(1)	O(n)	O(n)
Sorted Linked List	O(n)	O(1)	O(1)
Balance BST	O(logN)	O(logN)	O(logN)
Binary Heap	O(logN)	O(1)	O(logN)

Binary Heaps

A binary heap is based on the Array-based representation of a complete binary tree which adheres to the heap ordered property.

Heap ordering property is:

1. A heap is a complete binary tree, meaning each level of the tree holds the maximum number of children before filling the next level.
2. Each nodes key is greater than those of its children (Max Heap order) or each nodes key is less than that of its children (Min Heap order)

The key to maintaining the heap order be it a min heap or max heap is based on the upHeap and downHeap operations used for pushing and popping items from the heap, the only difference needed for implementing a min or max heap is the comparator being used.

The trick for ensuring that a complete binary tree is maintained is by using the ordering property of an array that:

If a nodes position is denoted as 'i', than 2*i+1 is the nodes left child, and 2*i+2 is the nodes right child. Combining this with filling an array from left to right with blank spaces ensures that we build a complete binary tree.

Armed with this knowledge we can construct efficient algorithms for maintaining a binary heap to implement our priority queue ADT.

Setting up the Priority Queue class

Before we get to implementing the heapify algorithms were going to outline the Priority Queue class.

The very first thing to know to know is that we will be implementing this as a template consisting of the following definition:

template <class Priority, class Item, class Comp> 
PriorityQueue { 

};

These template arguments give a typename to the values:

1. Priority - the data type by which the items will be ranked

2. Item - the associate data being ranked

3. Comp - the comparator being used to order the items by priority.

The second thing to know is that we will be using std::pair to associate Items and Priorities.

And third: An array of the above mentioned pair's will be the array we are implementing the heap operations upon.

With the ground work in place we can start outlining our class definitions:

Sift up(upHeap)

This operation is used when inserting a priority queue at the bottom and then "bubbling" the value up to its proper place in the heap. It's a very simple operation utilizing a comparator and a swap operation in a loop. Its goal is to move an item from the k'th position (usually the last) into its proper heap-ordered position, thus building the heap from the bottom up during push() operations.

Sift Down(downHeap)

downHeap, or "Top Down Heapify" is used when swapping an item out of the heap, as this is accomplished by swapping the root item with the last value in the heap array and reducing the array size by one, and then reordering the heap. While this may seem convoluted, it avoids the expensive processing of having to move every single item in the array over one space every time we remove an item from the heap. This is also the main heap operation used in heap sort.

getPriority(pop())

As explained in the above section on down heap, we accomplish this by swapping the root item with the last array position, decrementing the array size, and calling downHeap.

Push

I personally don't like the idea of a statically sized priority queue. Sizing the heap array too large and your wasting memory, size the heap too small and you risk overflow. To avoid having to deal with either of these situations i borrowed a page from the vector data structures playbook, and when the array is in danger of becoming full, i rellocate a new array a little less than twice the size of the current, copy everything to that array, and keep it moving. This isn't strictly necessary, but its not exactly difficult and makes for a much smoother user experience.

isEmpty() and size()

These are too simple checks which i'm including for completeness, but i don't believe they require explaining.

A full functioning priority queue

Now that we have all the pieces in place (a full implementation can be found on my github: https://github.com/maxgoren/MGCLib/blob/main/mgc_heap_priority_queue.hpp) It's time to give her a test drive. Thanks to our use of a comparator instead of hardcoding operators we can make either a Min Heap or Max Heap as the need arrises. Lets write a quick little program to demonstrate their usage:

I'm taking the string "PRIORITYQUEUE" and generating a random priority between 0 and 50 for each character. The same priority/character pair is used to build both a min heap and max heap. You can see when the values are then popped from their respective priority queues, they are in reverse order to each other. Clearly our algorithm can construct both a min and max heap just by passing different comparators!

Wrapping Up

There are many different underlying data structures that can be used to implement a priority queue. The binary heap i demonstrated is by far the most popular, but implementations abound using binomial queues, pairing heaps, leftist heap, fibonacci heaps, concurrent skip lists, and on and on and on. i encourage you to go out, research, explore, test, and come up with the implementation that fits your particular needs best!

Until next time,

-max

---