Priority Queues and Heaps
1
Lecture 21 (Data Structures 5)
CS61B, Fall 2024 @ UC Berkeley
Slides credit: Josh Hug
Introducing the Priority Queue
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Priority Queue Summary
Data Structures Summary
The Priority Queue Interface
Useful if you want to keep track of the “smallest”, “largest”, “best” etc. seen so far.
/** (Min) Priority Queue: Allowing tracking and removal of the
* smallest item in a priority queue. */
public interface MinPQ<Item> {
/** Adds the item to the priority queue. */
public void add(Item x);
/** Returns the smallest item in the priority queue. */
public Item getSmallest();
/** Removes the smallest item from the priority queue. */
public Item removeSmallest();
/** Returns the size of the priority queue. */
public int size();
}
Using a PQ
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Priority Queue Summary
Data Structures Summary
Usage Example: Recording the Highest Energy Particles
Suppose we have a particle detector that records the energy of incoming particles.
Suppose we want to record the M highest energy particles in a given day.
Naive approach: Create a list of all particles detected during the day. Sort it using a particle energy comparator. Return the M particles that have highest energy.
Naive Implementation: Store and Sort
Potentially uses a huge amount of memory Θ(N), where N is number of particles.
public List<Particle> highestEnergyParticles(Detector det, int M) {
ArrayList<Particle> allParticles = new ArrayList<>();
for (Timer timer = new Timer(); timer.hours() < 24; ) {
allParticles.add(det.getNextParticle());
}
Comparator<String> cmptr = new EnergyComparator();
Collections.sort(allParticles, cmptr, Collections.reverseOrder());
return allParticles.sublist(0, M);
}
Naive Implementation: Store and Sort
Potentially uses a huge amount of memory Θ(N), where N is number of particles.
public List<Particle> highestEnergyParticles(Detector det, int M) {
ArrayList<Particle> allParticles = new ArrayList<>();
for (Timer timer = new Timer(); timer.hours() < 24; ) {
allParticles.add(det.getNextParticle());
}
Comparator<String> cmptr = new EnergyComparator();
Collections.sort(allParticles, cmptr, Collections.reverseOrder());
return allParticles.sublist(0, M);
}
MinPQ<Particle> highEnergyParticles = new HeapMinPQ<>(cmptr);
Try to Solve Using a MinPQ
Potentially uses a huge amount of memory Θ(N), where N is number of particles.
public List<Particle> highestEnergyParticles(Detector det, int M) {
Comparator<Particle> cmptr = new EnergyComparator();
MinPQ<Particle> highEnergyParticles = new HeapMinPQ<>(cmptr);
for (Timer timer = new Timer(); timer.hours() < 24; ) {
// Do something with det.getNextParticle(); ??
...
}
MinPQ<Particle> highEnergyParticles = new HeapMinPQ<>(cmptr);
Better Implementation: Track the M Best
Can track top M transactions using only M memory. API for MinPQ also makes code very simple (don’t need to make explicit comparisons).
public List<Particle> highestEnergyParticles(Detector det, int M) {
Comparator<Particle> cmptr = new EnergyComparator();
MinPQ<Particle> highEnergyParticles = new HeapMinPQ<>(cmptr);
for (Timer timer = new Timer(); timer.hours() < 24; ) {
highEnergyParticles.add(det.getNextParticle());
if (highEnergyParticles.size() > M)
{ highEnergyParticles.removeSmallest(); }
}
ArrayList<String> returnList = new ArrayList<String>();
while (highEnergyParticles.size() > 0) {
returnList.add(highEnergyParticles.removeSmallest());
}
return returnList;
}
Some Bad Implementations
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Priority Queue Summary
Data Structures Summary
How Would We Implement a MinPQ?
Some possibilities:
| Ordered Array | Bushy BST | Hash Table | Heap |
add | Θ(N) | Θ(log N) | Θ(1) | |
getSmallest | Θ(1) | Θ(log N) | Θ(N) | |
removeSmallest | Θ(N) | Θ(log N) | Θ(N) | |
Caveats | | Dups tough | | |
Worst Case Θ(·) Runtimes
Heap Definitions
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Priority Queue Summary
Data Structures Summary
Introducing the Heap
BSTs would work, but need to be kept bushy and duplicates are awkward.
Binary min-heap: Binary tree that is complete and obeys min-heap property.
0
5
8
0
8
1
2
6
5
8
0
8
1
2
5
4
0
8
1
6
Incomplete
Lacks min-heap property
5
8
0
8
1
8
Heap Comprehension Test
How many of these are min heaps?
8
8
8
8
8
8
6
8
5
7
2
3
4
0
7
9
5
1
0
Heap Comprehension Test
How many of these are min heaps?
8
8
8
8
8
8
6
8
5
7
2
3
4
0
7
9
5
1
0
Incomplete
Lacks min-heap property
What Good Are Heaps?
Heaps lend themselves very naturally to implementation of a priority queue.
Hopefully easy question:
5
8
0
8
1
6
Heap Add
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Priority Queue Summary
Data Structures Summary
How Do We Add to a Heap?
Challenge: Come up with an algorithm for add(x).
Runtime must be logarithmic.
3
5
1
6
1
3
5
7
7
8
5
6
Heap Add Demo
Insert 3?
5
5
1
6
1
3
6
7
7
8
Heap Add Demo
Insert 3.
5
5
1
6
1
3
6
7
7
8
3
Heap Add Demo
Insert 3.
5
5
1
6
1
3
6
7
7
8
3
Heap Add Demo
Insert 3.
5
3
1
6
1
3
6
7
7
8
5
Heap Add Demo
Insert 3.
3
5
1
6
1
3
6
7
7
8
5
Heap Add Demo
Insert 3.
3
5
1
6
1
3
6
7
7
8
5
This is my true place.
Heap Add Demo
Insert 5.
3
5
1
6
1
3
6
7
7
8
5
5
Heap Add Demo
Insert 5.
3
5
1
6
1
3
6
7
7
8
5
5
Heap Add Demo
Insert 5.
3
5
1
6
1
3
5
7
7
8
5
6
Heap Add Demo
Insert 5.
3
5
1
6
1
3
5
7
7
8
5
6
I am home. For the first time in my life. I am home.
Heap Delete
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Priority Queue Summary
Data Structures Summary
How Do We Remove from a Heap?
Challenge: Come up with an algorithm for removeSmallest().
Runtime must be logarithmic.
5
5
3
6
3
6
5
7
7
8
Heap Delete Demo
Delete min.
3
5
1
6
1
3
5
7
7
8
5
6
Heap Delete Demo
Delete min.
3
5
1
6
1
3
5
7
7
8
5
6
Heap Delete Demo
Delete min.
3
5
1
6
1
3
5
7
7
8
5
6
What’s happening to me??
Wuh oh...
Heap Delete Demo
Delete min.
3
5
6
1
3
5
7
7
8
5
6
What’s happening to me??
Heap Delete Demo
Delete min.
3
5
6
1
3
5
7
7
8
5
6
I’m not cut out for this...
Move aside, cretin.
Heap Delete Demo
Delete min.
3
5
6
6
3
5
7
7
8
5
1
Heap Delete Demo
Delete min.
3
5
6
3
6
5
7
7
8
5
1
Heap Delete Demo
Delete min.
3
5
6
3
6
5
7
7
8
5
1
Heap Delete Demo
Delete min.
3
5
6
3
6
5
7
7
8
5
ulp...
Heap Delete Demo
Delete min.
3
5
6
3
6
5
7
7
8
5
Break tie arbitrarily.
Heap Delete Demo
Delete min.
5
5
6
3
6
5
7
7
8
3
I won’t descend further.
Recursive Representation (1)
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Priority Queue Summary
Data Structures Summary
Heap Operations Summary
Given a heap, how do we implement PQ operations?
Remaining question: How would we do all this in Java?
How do we Represent a Tree in Java?
Approach 1a, 1b and 1c: Create mapping from node to children.
w
x
y
z
1a: Fixed-Width Nodes (BSTMap used this approach)
public class Tree1A<Key> {
Key k; // e.g. 0
Tree1A left;
Tree1A middle;
Tree1A right;
...
w
z
x
y
How do we Represent a Tree in Java?
Approach 1a, 1b and 1c: Create mapping from node to children.
w
x
y
z
1b: Variable-Width Nodes
w
z
x
y
public class Tree1B<Key> {
Key k; // e.g. 0
Tree1B[] children;
...
How do we Represent a Tree in Java?
Approach 1a, 1b and 1c: Create mapping from node to children.
w
x
y
z
1c: Sibling Tree
public class Tree1C<Key> {
Key k; // e.g. 0
Tree1C favoredChild;
Tree1C sibling;
...
w
z
x
y
How do we Represent a Tree in Java?
Approach 1a, 1b and 1c: Create mapping from node to children.
w
x
y
z
w
x
y
z
w
x
y
z
1a: Fixed-Width Nodes
1b: Variable-Width Nodes
1c: Sibling Tree
w
z
x
y
Array Representations (2, 3, 3b)
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Priority Queue Summary
Data Structures Summary
How do we Represent a Tree in Java?
Approach 2: Store keys in an array. Store parentIDs in an array.
w
x
y
z
e
b
g
a
d
f
j
v
p
y
m
r
x
k
0
1
2
3
4
5
6
7
Key[] keys
int[] parents
0
0
0
0
k
e
v
b
g
p
y
a
d
f
j
m
r
x
Key[] keys
int[] parents
0 1 2 3
0 1 2 3 4
5 6 7 8 9 10 11 12 13
0
0
0
1
1
2
2
3
3
4
4
5
5
6
0 1 2 3 4
5 6 7 8 9 10 11 12 13
8
9
10
11
12
13
public class Tree2<Key> {
Key[] keys;
int[] parents;
...
w
z
x
y
How do we Represent a Tree in Java?
Approach 3: Store keys in an array. Don’t store structure anywhere.
w
x
y
z
e
b
g
a
d
f
j
v
p
y
m
r
x
k
0
1
2
3
4
5
6
7
Key[] keys
k
e
v
b
g
p
y
a
d
f
j
m
r
x
Key[] keys
0 1 2 3 4
5 6 7 8 9 10 11 12 13
8
9
10
11
12
13
0 1 2 3
public class Tree3<Key> {
Key[] keys;
...
w
z
x
y
A Deep Look at Approach 3
Challenge: Write the parent(k) method for approach 3.
w
x
y
z
e
b
g
a
d
f
j
v
p
y
m
r
x
k
0
1
2
3
4
5
6
7
Key[] keys
w
z
x
y
k
e
v
b
g
p
y
a
d
f
j
m
r
x
Key[] keys
0 1 2 3 4
5 6 7 8 9 10 11 12 13
8
9
10
11
12
13
0 1 2 3
public class Tree3<Key> {
Key[] keys;
...
public void swim(int k) {
if (keys[parent(k)] ≻ keys[k]) {
swap(k, parent(k));
swim(parent(k));
}
}
A Deep Look at Approach 3
Challenge: Write the parent(k) method for approach 3.
w
x
y
z
e
b
g
a
d
f
j
v
p
y
m
r
x
k
0
1
2
3
4
5
6
7
Key[] keys
k
e
v
b
g
p
y
a
d
f
j
m
r
x
Key[] keys
0 1 2 3 4
5 6 7 8 9 10 11 12 13
8
9
10
11
12
13
0 1 2 3
public class Tree3<Key> {
Key[] keys;
...
public void swim(int k) {
if (keys[parent(k)] ≻ keys[k]) {
swap(k, parent(k));
swim(parent(k));
}
}
public int parent(int k) {
return (k - 1) / 2;
}
w
z
x
y
Tree Representations (Summary)
w
x
y
z
w
x
y
z
w
x
y
z
1a: Fixed Number of Links (One Per Child)
1b: Array of Child Links
1c: FirstBorn/Sibling Links
w
x
y
z
Key[] keys
int[] parents
0
0
0
0
0 1 2 3
w
x
y
z
Key[] keys
2: Array of Keys, Array of Structure
3: Array of Keys
w
z
x
y
Approach 3B (book implementation): Leaving One Empty Spot
Approach 3b: Store keys in an array. Offset everything by 1 spot.
w
x
y
z
e
b
g
a
d
f
j
v
p
y
m
r
x
k
1
2
3
4
5
6
7
8
Key[] keys
w
z
x
y
k
e
v
b
g
p
y
a
d
f
j
m
r
x
Key[] keys
0 1 2 3 4
5 6 7 8 9 10 11 12 13 14
9
10
11
12
13
14
-
0 1 2 3 4
-
Priority Queue Summary
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Priority Queue Summary
Data Structures Summary
Heap Implementation of a Priority Queue
Notes:
| Ordered Array | Bushy BST | Hash Table | Heap |
add | Θ(N) | Θ(log N) | Θ(1) | Θ(log N) |
getSmallest | Θ(1) | Θ(log N) | Θ(N) | Θ(1) |
removeSmallest | Θ(N) | Θ(log N) | Θ(N) | Θ(log N) |
Items with same priority hard to handle.
Some Implementation Questions
/** (Min) Priority Queue: Allowing tracking and removal of the
* smallest item in a priority queue. */
public interface MinPQ<Item> {
/** Adds the item to the priority queue. */
public void add(Item x);
/** Returns the smallest item in the priority queue. */
public Item getSmallest();
/** Removes the smallest item from the priority queue. */
public Item removeSmallest();
/** Returns the size of the priority queue. */
public int size();
}
Data Structures Summary
Lecture 21, CS61B, Fall 2024
Priority Queue Introduction
Heaps
Tree Representations
Data Structures Summary
The Search Problem
Given a stream of data, retrieve information of interest.
Search Data Structures (The particularly abstract ones)
Name | Storage Operation(s) | Primary Retrieval Operation | Retrieve By: |
List | add(key) insert(key, index) | get(index) | index |
Map | put(key, value) | get(key) | key identity |
Set | add(key) | containsKey(key) | key identity |
PQ | add(key) | getSmallest() | key order (a.k.a. key size) |
Disjoint Sets | connect(int1, int2) | isConnected(int1, int2) | two int values |
Diagram of Data Structures and ADTs (past semester version)
PQ
List
Set
Map
DisjointSets
Chaining HT
Linear Probing HT
LinkedList
Resizing Array
Heap
Red Black
BST (Vanilla)
B-Trees (2-3 / 2-3-4)
Heap
Chaining HT (lacks order, very odd)
Ordered Linked List
Balanced Tree
Resizing Array
LinkedList
Quick Find
Quick Union
Weighted QU
WQUPC
Stack
Diagram of Data Structures and ADTs (past semester version)
Abstraction often happens in layers!
PQ
Heap Ordered Tree
Separate Chaining HT
Array of Buckets
Bucket
ArrayList
Resizing Array
LinkedList
BST (requires comparable items)
Tree
Approach 1A
Approach 1B
Approach 1C
Approach 2
Approach 3
Approach 3B
HashSet (weird choice)
Diagram of Data Structures and ADTs (past semester version)
Specialized Searching Data Structures:
Set
PQ
Map
Sorted Set
Sorted Map
2-3 Tree
RedBlack
BST
In Java:
java.util.SortedSet
java.util.SortedMap
List
Stack
Queue
Deque
Linked List
Resizing Array (slightly suboptimal due to resizing)
Don’t usually consider MinPQ and MaxPQ to be different data structures, since we can just provide the opposite comparator.
Data Structures
Data Structure: A particular way of organizing data.