Priority Queue in TypeScript
Sorted and heap-based priority queues explained
Queues and stacks are used in programming to process a collection of items in a certain order. Those data structures work either with a first-in-first-out or last-in-first-out system in which the order of processing is always directly coupled to the order of insertion. However, sometimes you need to have more control over the processing order then offered by the insertion order. The priority of items in the queue can depend on several external factors and some of the items will then have to (partially) skip the queue.
This concept is abstracted into a data structure called the priority queue. A priority queue differs from regular queues that items get inserted with a priority that determines when they will be returned by pop. The interface of a priority queue is very similar to that of a normal queue, only the insert method has gotten a second argument: the priority. The priority is expressed with a number. The convention is that a lower number means a higher priority and the connected item will be processed earlier then an item with a higher number.
Implementing the priority queue
They are several ways to implement a priority queue. We will start of by the simplest: the unsorted list (actually JavaScript array in our context). Here we use a JavaScript array to store pairs of priority and item. On insert we just push the items to the array, meaning the the array is ordered on the insertion order. When we want to query for the next item we iterate over the array and return the item with the lowest priority:
We can control first-in-first-out of last-in-first-out behavior by using either < or ≤ as our comparator operator when finding the lowest priority. This implementation has very fast inserts, but querying is a bit slow because we have to always iterate the entire array to find the item with the lowest priority.
Sorted priority queue
A different way to implement a priority queue around a linear data structure is to insert the items sorted by priority. This means that pop and peek can always just return the first item, but that insert has to iterate the contents to find the correct spot for the item.
Here we can also choose between first-in-first-out of last-in-first-out queuing by either using a > or ≥ comparator in the insert method. This version of the priority queue has fast querying, but slower insertion. Which one is the best choice depends on your use case: do you need fast inserts or fast queuering?
There is also an implementation that offers both good insertion and query performance. This uses a tree-based data structure instead of a linear data structure.
Heap-based priority queue
A heap is a binary tree that stores key-value pairs with the the item with the lowest key at the top. Inside a heap there has always to be a heap-order: the keys of the children have to be bigger than the key of the parent node. Or: if you go down, the keys go up. There are no rules about the ordering between left and right children, like you have in a binary search tree.
Heaps are usually displayed and reasoned about as trees, but most implementations actually use an array to store the data. This is possible because we can calculate the array index of a node or a child by doing some calculations on the indexes. And the arrays have one big pro over trees: it is possible to get the parent of a node, something that a in a traditional linked tree isn’t possible because the node doesn’t store a pointer to its parent. This greatly simplifies some of the code that is need to build a heap, especially when sorting you use the child-parent relation a lot to compare keys and swap items (also a lot easier with an array).
Let’s first define a basic structure for our new priority queue. We can already define the isEmpty, peek and size method as they only look to the root node and don’t modify the tree:
The main question you should have now is: how do we store a tree as an array? Well, if you have a tree you have multiple horizontal rows of nodes next to each other. You take all the horizontal rows and append them together into one array of nodes. This show in the image below.
If your tree has no empty spots except on the right of the last row (meaning at the end of the array) you can use basic algebra to figure out where each row start and which nodes are connected with each other. We will add those as helper functions inside our priority queue so we can just reason about left, right and parent nodes in the rest of our code.
There are two operations on heap-array that aren’t as trivial as the others: insert and pop. For both we need to not just add or remove an item, but also the reorder the array to again be a valid heap with a heap-order.
To insert a new node we start of by appending it to the array. This means it does occupy the most right empty spot on the bottom row or does starts a new row. When we do this we keep the tree valid and are able to traverse it with our helpers, but we still need to restore the heap-order. For this we compare the key of the new node to the key of its parent. If the key of the parent is bigger then the key of the new node we swap them around. This process gets repeated until we have got a parant for our the current node with a smaller key then the new node or the new node is at the top of the tree.
To implement pop we have to remove the first item of the array and restore the tree. Removing the first item means we chop the root node of our tree and we are left with two trees (that previously made up the left and right subtree of the root). This is not a valid state for a tree so we have to take a slightly longer route. What we do is we first swap the last item and the first item of the array. This means that the ‘root’ is now in the bottom-right corner and we can safely remove it with corrupting our tree. One thing that is still left to do is to restore heap-order in the heap. We do this by pushing our new root down the tree by swapping the current node with its smallest child until we again have our order.
And with this we have implemented the complete PriorityQueue interface with a heap and with both good insertion and querying performance. In a heap-based priority queue there is no relation between the order of insertion and the order in which entries with equal priorities will be processed.
Conclusion
In this article we have looked at what a priority queue is and at how we can implement it. As shown, a heap based priority queue gives the best overall performance.
