A Developer Introduction to Heaps and Priority Queues

How are they related?

Heap of Logs!

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:

  1. Shape: All levels of the tree must be filled, except for the last one. The last level must be filled from left to right.
  2. Order: All children should be greater than (min heap) or less than (max heap) their parent.
An example of a min heap and a max heap

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.

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.

Example insertion into a min 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.

Min heap deletion

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).

Heaps are often implemented using arrays. Let’s look at our min heap below.

An example min heap

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

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.

Example priority queue for letters of the alphabet

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.

Senior Software Engineer at the BBC

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store