Data Structures: Priority Queue
In the last post, we discussed creating a max binary heap. Today we will make a priority queue which is essentially a min binary heap. In a regular queue, we operate by using FIFO (first in first out). An example of this is people waiting in line to check out at the grocery store. A priority queue is a bit different. In our previous example, the first person in line was the first to be helped. What if the scenario changed a bit? How about the second person in line needed to buy his medication because of an emergency and the first person was simply doing a weekly grocery run. We all can agree that the second person should have priority and be helped first. This simple concept is what a priority queue works on. If all individuals have the same priority we would operate on the FIFO principle, but as soon as they have different priorities we need to serve the higher priority customers first.
Creating the heap is easy using a class. We also need a Node class.
Classes
We need to add two methods, enqueue and dequeue, which allow us to add and remove the priority queue.
Get jesse kovash’s stories in your inbox
Join Medium for free to get updates from this writer.
Enqueue
As discussed earlier we need to know a value as well as a priority level. In our code, a lower number will signal a higher priority. The first step is to create a new node and push it into our priority queue array (this.values). Next, we need to ‘bubble’ the node upward to find its position. This is done by checking if the current node value is less than its parent. If this is true, swap the nodes. Reassign the currIndex, parentIndex, and repeat. As soon as the current node value is greater than its parent we can break since it is in the correct position.
Dequeue
The next method we need is to remove the highest priority node from our priority queue. This is accomplished by swapping the first and last nodes and popping off the priority queue. What this does is move the lowest priority node to index 0 and remove the highest priority node. However, our priority queue is now in an incorrect order. We need to sink the lower priority node downwards to find its position. On each iteration we need to check if a swap needs to be made. If the left child priority is less than the current priority set ‘swap’ to be the left child index. Make sure to remember that a smaller number equals higher priority. Next, check the right child priority. If ‘swap’ is still null, we can simply check if the right priority is less than the current. However, if the ‘swap’ is not null, we need to also check if the right priority is less than the left. At the end of each iteration don’t forget to check if ‘swap’ is true. If so, swap the values, otherwise the current node is in the correct position and we can break.
If you read through the last post on a max binary heap you can see our code is nearly identical except for the comparison operators and method names changing. In the future we will be using our binary heap when implementing traversal methods on different data structures.
