• Java

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

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;  52  53 // Put the last node at the place of the root node.  54  55 arr = 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.