This post may contain affiliate links. Please see my full disclosure policy for details.
I recently visited the problem of creating a priority queue. I don’t think I’ve ever had created one from scratch. I’m not even sure that I understood the whole binary heap thing until I got deep into this problem.
I won’t attempt to re-create another blog post on how to create one but rather I will explain some key learning points, provide the resources that I used and provide the code that I used after using these resources.
It’s Easy to Keep a Tree Sorted
On an abstract level, the priority queue uses a tree to enable it to pull the next item off the queue. A normal queue allows you to pull the next item just as easily from an array. You could technically use a regular ordered array without using a binary tree but… That would mean that keeping it sorted would require shifting every item to the left or right of the item to be processed or deleted. That means that it would require O(n/2) or O(n) to insert an item. It would equally O(n) to remove an item. It could potentially take O(1) if you decided to shift the position of the front instead of shifting everything over.
Using an abstract tree instead takes O(log N) to insert and it takes O(log N) to remove.
Alternatively, you can use a linked list but that would add even more overhead and you would still need to search O(N) to find the insertion point.
Why Not Use A Real Tree with Left and Right Nodes
Keeping a heap tree within the constraints is tougher with a real tree. It would require the tree to be heapified from a list or array.
It’s much easier to keep a heap tree in an array.
A Heap Tree Has The Left and Right Child that is smaller or greater than the parent
Depending on if you have a min or a max. If you have a min that means that the root will always be the lowest value. For a max heap, the root will always be the highest.
With an array, it’s easy to insert a new value because it is always the last place (or next place in the array) in the array. In other words, it’s the size of the array. If the size of the tree is 1 the item goes in index 1. If it’s 2 then the next item goes in two.
The algorithm for insertion is so easy because then all you have to do is bubble up the item until it can go no further.
A Priority Queue layout of a tree
If you had the following tree
0 / \ 20 . 40 / \ / \ 30 35 50 45
It would look like the following array
[0, 20, 40, 30, 35, 50, 45]
Notice how the array follows the tree order from left to right and top to bottom.
So… on an insert, you would simply inert the item after 45. But what if the value breaks the rules. For example what if the value is 12. Well, that is why bubble up is during an insert.
So basically the tree would now look like this
0 / \ 20 40 / \ / \ 30 35 50 45 / 12
Since 12 breaks the rules (both child nodes must be greater than the parent), bubble up must be called on the tree.
It’s easy enough to bubble up because we must just compare the child with the parent and swap out if out of sequence.
Just keep moving 12 up until it finds a resting location in this case 12 would move up to this point
0 / \ 12 40 / \ / \ 20 35 50 45 / 30
Removing (dequeueing) the Next Item
Thinking of a tree but implementing it as a tree seems almost unnatural but when you consider how easy it is for this case, it may change your perspective.
Since we are always adding items at the end we always have a balanced tree. Well… to a degree. Much of the time the left will have more nodes due to the lowest level on the tree. Nonetheless, this allows us to always add at the end and then just use bubble up and bubble down.
For removing it’s equally easy. Just swap the first and last elements and then bubble the root down since there is a chance that the tree is not in compliance with a heap tree.
See the example in three steps as we remove the root item zero.
Step 1 – Swap first and last nodes
30 / \ 12 40 / \ / \ 20 35 50 45 / 0
Step 2 – Remove the last node and process it
30 / \ 12 40 / \ / \ 20 35 50 45
Step 3 – Bubble down the root until it finds its resting location
12 / \ 20 40 / \ / \ 30 35 50 45
Notice that I sent 30 down the left branch. You would think that it went down the left because that’s the original direction it came from. That is not the case at. The real reason is that 12 is the smaller of the two children 12 and 40. So… it goes in the direction of the smaller child.
That process of choosing to go left or right is repeated as it navigates its path down the tree.
Performing these steps will always have the tree in the right sequence ready to process the next item in the queue.
Finding Left Child, Right Child, and Parent
Since the tree is just an abstraction and it’s actually stored it’s in an array you may think it’s a challenge to find the parent, left and right child of a node. In all actuality, it’s pretty easy.
That is because it just takes some simple math.
For example to find the left and right child of index 0 we use the following formula
leftChildIndex = 0 * 2 + 1 or simply 1 rightChildIndex = 0 * 2 + 2 or simply 2
For index 1 we do the same formula
leftChildIndex = 1 * 2 + 1 or simply 3 rightChildIndex = 1 * 2 + 2 or simply 4
This formula works for any index. In essence, the formula is simply
leftChildIndex = idx * 2 + 1 rightChildIndex = idx * 2 + 2
The formula for finding the parent is just as easy
if(index % 2 == 0) parent = (index-1) / 2 else parent = index / 2
The reason for the if-check is that if the parent is 2, for example, we must remove 1 and divide by 2 which gives us 0. If we don’t subtract 1 we would get 1 as the parent of 2.
*By the way the code linked has this flaw… do you why it still seems to work?
There you have all the points I want to make about priority queues using heap trees.
Take a look at the links below to see the additional tutorials and source code companion.
Please remember to follow me on twitter @fernandozamoraj
Really Good Youtube Videos: https://youtu.be/wptevk0bshY
Recommended Book on more algorithms:
I personally recommend this book if you want to learn more about algorithms and data structures.