# Introduction

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

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

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

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

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

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

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

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

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

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

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

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.