Heaps and Priority Queues

Robert Horvick
SOFTWARE ENGINEER

@bubbafat www.roberthorvick.com
 Heap Overview
- Min and Max Heaps
Overview
Tree as Array
Heap Operations
- Push
- Pop
- Top
Priority Queue
Heap
A tree-based container type that provides O(1) access to
the minimum (min-heap) or maximum (max-heap) value
while satisfying the heap property.
Heap Property
The value in the current tree node is greater than, or
equal to, its children (max-heap).
 Heaps

Max-heap Min-heap

8 1

5 6 3 2

4 2 1 3 8 4 5 6
Satisfies the heap property

The tree is a complete tree

 1
Satisfies the heap property

The tree is a complete tree 3 2

8 4 5 6
Min-heap
 1
Satisfies the heap property

The tree is a complete tree 3 2

8 4 5 6
 1
Satisfies the heap property

The tree is a complete tree 3 2

8 4 5 6
 1
Satisfies the heap property

The tree is a complete tree 2 4

8 3 5 6
 8
Satisfies the heap property

The tree is a complete tree 5 6

4 2 1 3
Max-heap
 8
Satisfies the heap property

The tree is a complete tree 5 6

4 2 1 3
Complete Tree
A tree where every level is filled out from left-to-right be
starting the next level.
 8
Satisfies the heap property

The tree is a complete tree

Complete tree
 8
Satisfies the heap property

The tree is a complete tree 5

Complete tree
 8
Satisfies the heap property

The tree is a complete tree 5 6

Complete tree
 8
Satisfies the heap property

The tree is a complete tree 5 6

4
Complete tree
 8
Satisfies the heap property

The tree is a complete tree 5 6

4 2
Complete tree
 8
Satisfies the heap property

The tree is a complete tree 5 6

4 2 1
Complete tree
 8
Satisfies the heap property

The tree is a complete tree 5 6

4 2 1 3
Complete tree
 8
Satisfies the heap property

The tree is a complete tree 6

Incomplete tree
 8
Satisfies the heap property

The tree is a complete tree 5 6

4 1
Incomplete tree
 8
Satisfies the heap property

The tree is a complete tree 5

4 2
Incomplete tree
Trees as Arrays
Complete binary trees can be compactly stored as arrays
eliminating all structural overhead and providing O(1)
data access.
 Tree as Array

1 2

3 4 5 6
7 8 9 10
 Tree as Array

1 2

3 4 5 6
7 8 9 10

0 1 2 3 4 5 6 7 8 9 10
 Tree as Array

Index 0 1 2 3 4 5 6 7 8 9 10
Parent x 0 0 1 1 2 2 3 3 4 4
Left 1 3 5 7 9 11 13 15 17 19 21
Right 2 4 6 8 10 12 14 16 18 20 22

0 1 2 3 4 5 6 7 8 9 10
 Tree as Array

Index 0 1 2 3 4 5 6 7 8 9 10
Parent x 0 0 1 1 2 2 3 3 4 4
Left 1 3 5 7 9 11 13 15 17 19 21
Right 2 4 6 8 10 12 14 16 18 20 22

0 1 2 3 4 5 6 7 8 9 10
 Tree as Array

Index 0 1 2 3 4 5 6 7 8 9 10
Parent x 0 0 1 1 2 2 3 3 4 4
Left 1 3 5 7 9 11 13 15 17 19 21
Right 2 4 6 8 10 12 14 16 18 20 22

int parent(const int index) {

return (index - 1) / 2;
}

0 1 2 3 4 5 6 7 8 9 10
 Tree as Array

Index 0 1 2 3 4 5 6 7 8 9 10
Parent x 0 0 1 1 2 2 3 3 4 4
Left 1 3 5 7 9 11 13 15 17 19 21
Right 2 4 6 8 10 12 14 16 18 20 22

int left(const int index) {

return 2 * index + 1;
}

0 1 2 3 4 5 6 7 8 9 10
 Tree as Array

Index 0 1 2 3 4 5 6 7 8 9 10
Parent x 0 0 1 1 2 2 3 3 4 4
Left 1 3 5 7 9 11 13 15 17 19 21
Right 2 4 6 8 10 12 14 16 18 20 22

int right(const int index) {

return 2 * index + 2;
}

0 1 2 3 4 5 6 7 8 9 10
Heap Operations
 Heap Operations

Adding values (push)

Retrieving min or max value (top)

Removing min or max value (pop)

Push
Adds an item to the heap, placing it in the first valid
position that retains the tree rules.
 Push Operations

Add the new value to the end of the While the heap property is not
heap array satisfied, swap the new item with its
parent
 8

Add new value to end of

heap
5 6
While the heap property is
not satisfied, swap with 4 2
parent

8 5 6 4 2
 8

Add new value to end of

heap
5 6
While the heap property is
not satisfied, swap with 4 2 9
parent

8 5 6 4 2
 8

Add new value to end of

heap
5 6
While the heap property is
not satisfied, swap with 4 2 9
parent

8 5 6 4 2 9
 8

Add new value to end of

heap
5 6
While the heap property is
not satisfied, swap with 4 2 9
parent

8 5 6 4 2 9
 8

Add new value to end of

heap
5 6
While the heap property is
not satisfied, swap with 4 2 9
parent

8 5 6 4 2 9
 8

Add new value to end of

heap
5 9
While the heap property is
not satisfied, swap with 4 2 6
parent

8 5 6 4 2 9
 8

Add new value to end of

heap
5 9
While the heap property is
not satisfied, swap with 4 2 6
parent

8 5 9 4 2 6
 8

Add new value to end of

heap
5 9
While the heap property is
not satisfied, swap with 4 2 6
parent

8 5 9 4 2 6
 8

Add new value to end of

heap
5 9
While the heap property is
not satisfied, swap with 4 2 6
parent

8 5 9 4 2 6
 9

Add new value to end of

heap
5 8
While the heap property is
not satisfied, swap with 4 2 6
parent

8 5 9 4 2 6
 9

Add new value to end of

heap
5 8
While the heap property is
not satisfied, swap with 4 2 6
parent

9 5 8 4 2 6
 9

Add new value to end of

heap
5 8
While the heap property is
not satisfied, swap with 4 2 6
parent

9 5 8 4 2 6
 9

Add new value to end of

heap
5 8
While the heap property is
not satisfied, swap with 4 2 6 3
parent

9 5 8 4 2 6 3
Top
Returns the first item (min or max) in the heap.
 Top

5 8

4 2 6

9 5 8 4 2 6
 Top

5 8

4 2 6

9 5 8 4 2 6
public T Top() {

if (Count > 0) {

return data[0];

throw new Exception("Top called on empty heap");

Top
Return the first item in the heap
Pop
Removes the top item from the heap, moving the
replacement item into the first valid position in the heap
tree.
 Pop Operations

Move the last item in the heap array While the heap property is not
into the zero (root) index satisfied, swap the item with one of
its children
 9

Replace top value with 5 8

right-most child

Swap new top value until

heap property is satisfied
4 2 6

9 5 8 4 2 6
 9

Replace top value with 5 8

right-most child

Swap new top value until

heap property is satisfied
4 2 6

9 5 8 4 2 6
 Replace top value with 5 8
right-most child

Swap new top value until

heap property is satisfied
4 2 6

9 5 8 4 2 6
 6

Replace top value with 5 8

right-most child

Swap new top value until

heap property is satisfied
4 2

9 5 8 4 2 6
 6

Replace top value with 5 8

right-most child

Swap new top value until

heap property is satisfied
4 2

6 5 8 4 2
 6

Replace top value with 5 8

right-most child

Swap new top value until

heap property is satisfied
4 2

6 5 8 4 2
 6

Replace top value with

right-most child
5 8
Swap new top with
children until heap 4 2
property is satisfied

6 5 8 4 2
 6

Replace top value with

right-most child
5 8
Swap new top with
children until heap 4 2
property is satisfied

6 5 8 4 2
 5

Replace top value with

right-most child
6 8
Swap new top with
children until heap 4 2
property is satisfied

5 6 8 4 2
 6

Replace top value with

right-most child
5 8
Swap new top with
children until heap 4 2
property is satisfied

6 5 8 4 2
 6

Replace top value with

right-most child
5 8
Swap new top with
children until heap 4 2
property is satisfied

6 5 8 4 2
 8

Replace top value with

right-most child
5 6
Swap new top with
children until heap 4 2
property is satisfied

6 5 8 4 2
 8

Replace top value with

right-most child
5 6
Swap new top with
children until heap 4 2
property is satisfied

8 5 6 4 2
 8

Replace top value with

right-most child
5 6
Swap new top with
children until heap 4 2
property is satisfied

8 5 6 4 2
 9

Replace top value with 7 8

right-most child

Swap new top value until

heap property is satisfied
4 2 6

9 7 8 4 2 6
 9

Replace top value with 7 8

right-most child

Swap new top value until

heap property is satisfied
4 2 6

9 7 8 4 2 6
 6

Replace top value with 7 8

right-most child

Swap new top value until

heap property is satisfied
4 2

6 7 8 4 2
 7

Replace top value with

right-most child
6 8
Swap new top with
children until heap 4 2
property is satisfied

7 6 8 4 2
 6

Replace top value with

right-most child
7 8
Swap new top with
children until heap 4 2
property is satisfied

6 7 8 4 2
 8

Replace top value with

right-most child
7 6
Swap new top with
children until heap 4 2
property is satisfied

8 7 6 4 2
Priority Queue
A queue that pops item in priority, not FIFO, order.
 Priority Queue

Job
Job 4
3
2
1
Priority Queue

Job 4
 Priority Queue

Job 3 Job 4
Priority Queue

Job 3 Job 4
 Priority Queue

Job 2 Job 3 Job 4

Priority Queue

Job 2 Job 3 Job 4

 Priority Queue

Job 1 Job 2 Job 3 Job 4

Priority Queue

Job 1 Job 2 Job 3 Job 4

 Priority Queue

Urgent! Job 1 Job 2 Job 3 Job 4

Priority Queue

Urgent! Job 1 Job 2 Job 3 Job 4

Priority Queue

Job 1 Job 2 Job 3 Job 4 Urgent!

public class PriorityQueue<T> { t Generic class

readonly Heap<T> heap = new Heap<T>(); t Data is stored in a heap

public void Enqueue(T value) { t Enqueue pushes a value onto the heap
heap.Push(value);

public T Deque() { t Deque pops a value from the heap

T value = heap.Top();

heap.Pop();

return value;

}
Demo
Review heap code
Review priority queue
Example: job queue