A Developer Introduction to Heaps and Priority Queues
How are they related?
Audience
This article is aimed at developers looking to be introduced to the heap data structure. We will begin by defining a heap, then exploring priority queues and the two structures’ relationship.
It will help if you are familiar with trees and queues, as they will underpin our heap representation. For a quick refresher try my tree article here, and my queue article here.
Argument
A heap is binary tree with two extra sets of constraints:
- Shape: All levels of the tree must be filled, except for the last one. The last level must be filled from left to right.
- Order: All children should be greater than (min heap) or less than (max heap) their parent.
On the left we have a min heap (the minimum is at the top). On the right we have a max heap (the maximum is at the top). Notice also how they are not necessarily binary search trees.
Inserting into a Heap
If we want to insert into a heap we need to put the next item in the next leftmost free space on the bottom layer in order to preserve our shape constraint.
However, this may then violate our order constraint. To restore this we need to look at the parent node of our new child and confirm it is greater (or less than, depending on heap type), our node.
We then continually do this and ‘bubble up’ the new value.
Deleting from a Heap
Deleting from a heap is slightly trickier. However, again we rely on our shape constraint. In order to keep in line with this limit we can only remove the rightmost node from the bottom layer.
We then replace the value from the node we are deleting with this value. From there we need to ‘bubble down’ the value to satisfy our order constraint.
We use the above tree as an example. We would like to delete the root, and therefore move the bottom right node into the spot for deletion. From there we compare it to the two child nodes. We will swap it with the smallest node as this is a min heap (if it was a max heap it would be the largest node).
Implementing a Heap
Heaps are often implemented using arrays. Let’s look at our min heap below.
We can represent this heap using the array
[5, 10, 7, 12, 11, 13, 15]We use the below formula to determine the indexes of a node’s relations, where i is the index of our current node.
2i + 1: Index of right child node.2i + 2: Index of left child node(i — 1)/2: Index of parent node
Priority Queues
Due to this array implementation, heaps are a great way to represent priority queues. These queues are similar to the regular implementation, except each item has a priority, with highest priority items being dequeued first. Items with equal priority are dequeued in the order they were inserted.
If we insert the letters A to G into a queue, with priority matching their alphabetic order, it would come out as below.
Our first priority item will always be our root, helping us retrieve it with complexity O(1) , whilst the tree structure provides us with O(log(n)) insertion and deletion times.
Conclusion
In conclusion, we have explored the definition of heaps, how to use them, their implementation and one of their most common applications.
