Learning Priority Queues
Last week, I wrote about my first foray into Binary Heaps, which can be found here. Having knowledge of heaps is really helpful when learning priority queues, since the optimal(but not only) way to implement them is with a heap. In last weeks post, I also had a link to a repl I made showing how to construct a max heap in JavaScript(here), as well as some essential methods to implement. I have added a priority queue class in that same repl.
What are priority queues?
A priority queue is an abstract data structure. It is a lot like a normal queue, except each node or element has a priority assigned to it in addition to its value. The nodes with the highest priority are removed from the queue first. If two elements have the same priority, whichever one was added to the queue first will be removed first.
There are a variety of different ways that we can implement priority queues. We could use an array, linked list, or a heap. Binary heaps lend themselves well to use as priority queues because Max Heaps and Min Heaps are organized based on the value of a node being less than or greater than the value of its parent, respectively. This means that a lot of the logic to create a priority queue already exists within heaps. Because heaps are so easy to use for priority queues, there is a common misconception that priority queues are heaps. While you should probably always use a heap for your priority queue, it is important to know that you don’t necessarily have to.
Why not an array or linked list?
If we were to use an array, the time complexity would be much greater. The greatest weakness of an array in terms of big O is re-indexing. For example, if we add an item to the beginning of an array, every single element after that needs to be re-indexed. Adding to the end is much more efficient, but unfortunately, that would not solve our problems, since the array would very soon not be in order of priority. At this point, we would have to iterate over the array to find out which item has the highest priority, which could take a really long time depending on the size of the array. While it would get the job done, a heap is a much more efficient tool. Linked Lists have similar time complexity issues to arrays for tasks like this.
Real-world applications
Priority queues are used under the hood by our computers all of the time to both make sure that the most important operations are being handled first. They are also used in data compression, and Djikstra’s Shortest Path Algorithm. However, the concept of a priority queue is not exclusive to computer science. The Covid-19 vaccine rollout is an excellent example of a priority queue. You could think of the elderly being the highest priority, followed by people with suppressed immune systems, essential workers, and so on. When priority is equal, such as two people who are in their 90’s, whoever called or applied for an appointment first(or ‘queued up’) will be the first to receive the vaccine.
The fun part
Now that you have a good idea of what a priority queue is(or, however good of an idea I have at least), here’s the code I used to implement a priority queue! I decided to make a Min Heap, since last week I made a Max Heap. A priority queue can be made with either. When using a Min Heap, the nodes with the lowest number of priority will be removed first. While this may seem counterintuitive, it is actually pretty common outside of programming for ‘priority 1’ to mean ‘of the greatest priority.’ This can of course be done with a Max Heap as well, just keep in mind that the highest priority value will be removed first.
First, here is the node class that I created. These nodes will make up our priority queue, and are relatively simple. There are no pointers or anything like that, just a value and the priority of that value.
Next, we have our basic priority queue, without any methods.
Here is our method for adding a new node to the queue.
And finally, here is the method for removing the highest priority item from the queue.
Thanks for reading, and I hope that you found this helpful and informative!
