Heaps and Priority Queues
Daniel Archambault
CS-115: Heaps and Priority Queues
1
Previously in CS-115
Hash Function
”Dan!”
”Swansea!” ”Oh No!”
3
0
1
1 2
3
3
4
Hash it in there with non-integer keys.
(”Swansea!”, 33)
(”Dan!, 27)
(”Oh No!”, 8)
CS-115: Heaps and Priority Queues
2
Previously in CS-115
What is a hash map?
CS-115: Heaps and Priority Queues
3
Previously in CS-115
What is a hash map?
What are the advantages of a hash map?
CS-115: Heaps and Priority Queues
3
Previously in CS-115
What is a hash map?
What are the advantages of a hash map? What is a hashing function?
CS-115: Heaps and Priority Queues
3
Previously in CS-115
What is a hash map?
What are the advantages of a hash map?
What is a hashing function?
What is a collision? How do we deal with collisions?
CS-115: Heaps and Priority Queues
3
Previously in CS-115
Now it’s time to get our priorities straight!
Heaps and Priority Queues
CS-115: Heaps and Priority Queues
4
Priority Queue ADT
Like a queue, but…
all items inserted into the queue have a priority
the front of the queue is always the item of highest priority
you can think of it as an emergency room
Like queues, you have enqueue, dequeue, peek, and isEmpty.
https://docs.oracle.com/javase/8/docs/api/java/
util/PriorityQueue.html
CS-115: Heaps and Priority Queues
5
Priority Queue ADT
public interface PriorityQueue {
public boolean isEmpty ();
public void enqueue (Object newItem); public Object dequeue ();
public Object peek ();
}
Similar to Queue, but all must have priorities
CS-115: Heaps and Priority Queues
6
isEmpty behaviour
Returns true if there are no elements in the priority queue Otherwise, returns false
(a) true
27
27
10
8
4
2
2
(b) false
CS-115: Heaps and Priority Queues
7
enqueue behaviour
Adds an item to the priority queue in the right priority order
27
27
10
8
4
2
2
(c) before enqueue of 18
27
27
18
10
8
4
2
2
(d) after enqueue This needs to be efficient.
CS-115: Heaps and Priority Queues
8
dequeue behaviour
Removes an item from the front of the priority queue The front is always the element of highest priority
27
27
18
10
8
4
2
2
(e) before dequeue d
27
18
10
8
4
2
2
(f) after dequeue This needs to be efficient.
CS-115: Heaps and Priority Queues
9
peek behaviour
Returns the front of the priority queue
27
18
10
8
4
2
2
(g) returns 27
CS-115: Heaps and Priority Queues
10
How do we do this?
We do this using another ADT call a Heap Usually, heaps are implemented with trees There are max heaps and min heaps
Max heaps keep the maximum at the top
Min heaps keep the minimum at the top
We will implement heaps with linked structures
CS-115: Heaps and Priority Queues
11
Insertion Order for Max Heaps
(a) (b) (c)
(d)
Heaps are trees that grow using level order of the tree
(e)
(f)
CS-115: Heaps and Priority Queues
12
Heap ADT Implemented with links
Every node of the tree is greater than both its children
27
27 8422
10
27
27
10
8
4
2
2
We don’t know the absolute order of priorities, but we always know the maximum priority!
Why? Root will always be the maximum by definition
CS-115: Heaps and Priority Queues
13
isEmpty Implementation
Check the tree. If root == null return true. 27
27 8422
10
27
27
10
8
4
2
2
CS-115: Heaps and Priority Queues
14
Enqueue Implementation
Insert item at leaves. If out of order, swap to correct order
27
10
27
27
27 8422
18
27
18 4 2 2
8
10
8422
27
10
27
27
18
10
8
4
2
2
CS-115: Heaps and Priority Queues
15
Dequeue Implementation
Insert item at leaves. If out of order, swap to correct order
27
27 10 27 10
18 4 2 2 18 4 2 2
88 27
10
18 4 2 2
8
27
18
10
8
4
2
2
CS-115: Heaps and Priority Queues
16
Dequeue Implementation
Insert item at leaves. If out of order, swap to correct order
27 27
18 10 18 10
4228422
8
27
18
10
8
4
2
2
CS-115: Heaps and Priority Queues
17
Peek Implementation
Return the contents of the root if not null
27
27 8422
10
27
27
10
8
4
2
2
CS-115: Heaps and Priority Queues
18
Insertions and Many Swaps
An insert could involve many swaps
27 27
18 10 18 10
8 4 2 2 33 4 2 2
33 8
27 33
33 10 27 10
18 4 2 2 18 4 2 2
88
CS-115: Heaps and Priority Queues
19
Dan! But How!
How can the swap implementation be implemented? Tree node has a reference to an element
to swap, compare the two keys
if child is greater than parent, swap the references of the elements
only
CS-115: Heaps and Priority Queues
20
Dan! But How! (2)
How do we do a level order traversal of a tree? You can use a queue!
27 27
8
10 422
…
…
CS-115: Heaps and Priority Queues
21
Summary
Priority Queues are one of the most complete data structures we can look at.
Involves a tree and a queue
Introduces a new ADT called a heap
It is just like a queue, but…
High priorities percolate up to the top of the queue.
CS-115: Heaps and Priority Queues
22