Background Image

ADS 0x04: Heaps & Priority Queues

Published December 15th, 2021

ADS Wallpaper

Introduction Get link to this section

Priority queues are handy data structures for implementing algorithms that need to process a lot of data with a certain priority. For example, in a game, you need to process a lot of entities that need to be updated. You can use a priority queue to keep track of the entities that need to be updated for performance reasons. Entities which are closer to the camera will have a higher priority and are rendered first.

It turns out heaps are the most efficient data structure for implementing priority queues. Heaps are dynamic data structures that implement the following operations:

  • Insertion in time.
  • Removal of the minimum or maximum element in time.

As you can see, those two operations are both very fast, and basically the most important operations for priority queues.


Heap Property Get link to this section

A simple max (or min) heap is a binary tree that satisfies the following two properties:

For each path you can take from the root to a leaf, the values you traverse must be in non-increasing (or non-decreasing) order. From this, we can conclude that the root of the tree is the largest (or smallest) element in the heap.

A heap must be a complete binary tree. This means that every level except the last must be completely filled, and the last level must be filled from left to right.

Let's look at some binary trees and see whether they are heaps or not. If they are heaps, then check whether they are max heaps or min heaps.

The above binary tree is a max heap. There are four paths we can take from the root to the children:

  • 9-4-3
  • 9-4-3
  • 9-8-2
  • 9-8-7
All of them are in non-increasing order, so it is a max heap.


The above binary tree is a min heap. There are four paths we can take from the root to the children:

  • 3-4-4
  • 3-4-7
  • 3-3-8
  • 3-3-5
All of them are in non-decreasing order, so it is a min heap.


The above binary tree is not a heap. There are four paths we can take from the root to the children:

  • 5-5-6
  • 5-5-5
  • 5-8-7
  • 5-8-9
5-8-7 first increases, and then decreases. So it is neither non-decreasing nor non-increasing. We have to conclude that it is not a heap.
Which two elements would we have to switch to make it a heap?


Heap Algorithms

Let's see how we can add and remove elements from a heap. These two operations are required for a priority queue.

Heap Add Get link to this section

In the above picture, we can see how we add an entry to a max heap. We put the new entry at the bottom of the tree, and then we bubble it upwards until it is in the correct position.

Putting the entry at the bottom of the tree takes time, and bubbling it upwards takes time, because we have to swap at most elements, since there are items in a path from the root to a leaf.
The total time complexity is therefore .

Heap Remove Get link to this section

To remove the maximum element from a max heap, we take out the root, which we will return later. Then we replace the root with the last element in the heap, and then we bubble the new root downwards until it is in the correct position.

With the same logic as in the add case, we can conclude that the time complexity is .

Array Trees Get link to this section

Since a heap works with a complete binary tree, we can also use a dynamic array to represent it. This array tree is much more performant than a linked tree, since we can access any node in constant time and dynamic arrays are much more efficient than linked lists.

The elements of the heap are put in the array in breadth-first order. This mean that the root is at index 0, the first level nodes are at indices 1 and 2, the second level nodes are at indices 3, 4, 5, 6 and so on. Since heaps are complete binary trees, there are no gaps in the array, and the array ends at the last existing element of the last level.

There are three formulas that we can use to get the parent and the children of any node in the array tree:



With these formulas, we can find the parent or children of any node.
For example, the parent of the node at index 3 is at index 1;
the left right of the node at index 1 is at index 4;
and the right child of the root node is at index 2.
The left child of the node at index 4 is at index 9. But the array only goes up to index 6, so the node at index 4 doesn't have a left child.


Basic Priority Queue Implementation Get link to this section

Let's implement an array-based heap priority queue in Java that supports removal of the root and insertion. The priority queue will be a max heap, so the root will have the highest priority.

  1 
// The type of elements in the priority queue must be comparable,
  2 
// because we need to be able to reorder the elements.
  3
  4 
class PriorityQueue<T extends Comparable<T>>
  5 
{
  6 
	public T[] arr
  7 
	public int size;
  8
  9 
	public
 10 
	PriorityQueue()
 11 
	{
 12 
		root = null;
 13 
		last = null;
 14 
		size = 0;
 15 
	}
 16
 17 
	private int
 18 
	leftChildIndex(int i)
 19 
	{
 20 
		return 2 * i + 1;
 21 
	}
 22
 23 
	private int
 24 
	rightChildIndex(int i)
 25 
	{
 26 
		return 2 * i + 2;
 27 
	}
 28
 29 
	private int
 30 
	parentIndex(int i)
 31 
	{
 32 
		return (i - 1) / 2;
 33 
	}
 34
 35 
	public void
 36 
	add(T value)
 37 
	{
 38 
		// Insert the new node at the end of the array.
 39
 40 
		arr[size] = value;
 41 
		size++;
 42
 43 
		// Bubble the new node upwards.
 44
 45 
		bubbleUp(size - 1);
 46 
	}
 47
 48 
	public T
 49 
	removeMax()
 50 
	{
 51 
		T max = arr[0];
 52
 53 
		// Put the last node at the place of the root node.
 54
 55 
		arr[0] = arr[size - 1];
 56 
		size--;
 57
 58 
		// Bubble the root node down.
 59
 60 
		bubbleDown(0);
 61
 62 
		return max;
 63 
	}
 64
 65 
	private void
 66 
	swap(int i, int j)
 67 
	{
 68 
		T temp = arr[i];
 69 
		arr[i] = arr[j];
 70 
		arr[j] = temp;
 71 
	}
 72
 73 
	private void
 74 
	bubbleUp(int index)
 75 
	{
 76 
		// This method bubbles a node up.
 77 
		// In each iteration, we check if the parent node exists,
 78 
		// and if it does, we will bubble the given element up if needed.
 79
 80 
		while (true)
 81 
		{
 82 
			if (index == 0)
 83 
			{
 84 
				// We reached the root of the array tree.
 85
 86 
				break;
 87 
			}
 88
 89 
			int parentIndex = parentIndex(index);
 90
 91 
			if (arr[parentIndex].compareTo(arr[index]) > 0)
 92 
			{
 93 
				// The parent is larger than the node,
 94 
				// so we should stop bubbling.
 95
 96 
				break;
 97 
			}
 98
 99 
			// Bubble the node up a level.
100
101 
			swap(index, parentIndex);
102 
			index = parentIndex;
103 
		}
104 
	}
105
106 
	private void
107 
	bubbleDown(int index)
108 
	{
109 
		// This method bubbles a node down.
110 
		// In each iteration, we check if the left and right children
111 
		// exist, and if they do, we take the largest among them and
112 
		// bubble the given node down if needed.
113
114 
		while (true)
115 
		{
116 
			int leftChildIndex = leftChildIndex(index);
117 
			int rightChildIndex = rightChildIndex(index);
118
119 
			if (leftChildIndex >= size)
120 
			{
121 
				// There is no left child.
122
123 
				break;
124 
			}
125
126 
			if (rightChildIndex >= size)
127 
			{
128 
				// There is only a left child.
129
130 
				if (arr[index].compareTo(arr[leftChildIndex]) > 0)
131 
				{
132 
					// The node is larger than the only child,
133 
					// so we should stop bubbling.
134
135 
					break;
136 
				}
137
138 
				// Bubble the node down a level.
139
140 
				swap(index, leftChildIndex);
141 
			}
142 
			else
143 
			{
144 
				if (arr[leftChildIndex].compareTo(arr[rightChildIndex]) > 0)
145 
				{
146 
					// The left child is larger than the right child.
147
148 
					if (arr[index].compareTo(arr[leftChildIndex]) > 0)
149 
					{
150 
						// The node is larger than the left child,
151 
						// so we should stop bubbling.
152
153 
						break;
154 
					}
155 
				}
156 
				else
157 
				{
158 
					// The right child is larger than the left child.
159
160 
					if (arr[index].compareTo(arr[rightChildIndex]) > 0)
161 
					{
162 
						// The node is larger than the right child,
163 
						// so we should stop bubbling.
164
165 
						break;
166 
					}
167 
				}
168 
			}
169 
		}
170 
	}
171 
}

The above is a lot of code, but it's mostly because of the bubbling methods are rather long. We are essentially just implementing the bubbling methods in the pictures above.

Heapify Get link to this section

Sometimes we would like to create a heap from an array of unsorted elements. We can do this by using the heapify algorithm. This algorithm will take an array and turn it into a heap in time.

A naive approach of the heapify algorithm would be to create a heap, and add each element to the heap. This would take time, which is worse.

The heapify algorithm is very simple: we go through the array in reverse order, and bubble down each element we are iterating over. You might think this would still take time, because we are performing a operation for each element, but this is not the case because the algorithm ensures we never bubble down twice over the same path.

We can see that we can create paths in a heap that only go over each edge once, and since the number of edges is equal to the number of nodes in the heap minus one, we can see that if we bubble down over unique paths, we will never bubble down twice over the same path. This is why the heapify algorithm takes time.

 1 
public PriorityQueue<T>
 2 
heapify(T[] arr)
 3 
{
 4 
	PriorityQueue<T> heap = new PriorityQueue<>();
 5 
	heap.arr = arr;
 6 
	heap.size = arr.length;
 7
 8 
	for (int i = size - 1; i > 0; i--)
 9 
	{
10 
		heap.bubbleDown(i);
11 
	}
12
13 
	return heap;
14 
}

Final Thoughts Get link to this section

Priority queues are a very useful data structure in many situations. They support insertion and removal, and can be implemented using a heap. An arbitrary array can be turned into a heap in time using the heapify algorithm.

I hope you enjoyed this post! Feel free to share it, and if you have any feedback, feel free to contact me.