CS61B, 2021
Lecture 20: Priority Queues and Heaps ● Priority Queues
● Heaps
● Tree Representations
● Data Structures Summary
The Priority Queue Interface
/** (Min) Priority Queue: Allowing tracking and removal of the
* smallest item in a priority queue. */
public interface MinPQ
/** 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();
}
Useful if you want to keep track of the “smallest”, “largest”, “best” etc. seen so far.
Usage Example: Unharmonious Texts
Imagine that you’re part of Grand Leader’s Information Compliance and Happiness Enhancement (GLICHE) team.
● Your job: Monitor the text messages of the citizens to make sure that they are not having any unharmonious conversations.
● Each day, you prepare a report of the M messages that seem most unharmonious using the HarmoniousnessComparator.
Naive approach: Create a list of all messages sent for the entire day. Sort it using your comparator. Return the M messages that are largest.
Naive Implementation: Store and Sort
public List
for (Timer timer = new Timer(); timer.hours() < 24; ) { allMessages.add(sniffer.getNextMessage());
}
Comparator
return allMessages.sublist(0, M);
}
Potentially uses a huge amount of memory Θ(N), where N is number of texts. ● Goal: Do this in Θ(M) memory using a MinPQ.
MinPQ
Better Implementation: Track the M Best
public List
{ unharmoniousTexts.removeSmallest(); }
}
ArrayList
textlist.add(unharmoniousTexts.removeSmallest());
}
return textlist; }
Can track top M transactions using only M memory. API for MinPQ also makes code very simple (don’t need to do explicit comparisons).
How Would We Implement a MinPQ?
Some possibilities:
● Ordered Array
● Bushy BST: Maintaining bushiness is annoying. Handling duplicate priorities
is awkward.
● HashTable: No good! Items go into random places.
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
Heaps
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.
● Min-heap: Every node is less than or equal to both of its children.
● Complete: Missing items only at the bottom level (if any), all nodes are as far
left as possible.
000
5151
00
5151
882846
8862886
Incomplete
Lacks min-heap property
Heap Comprehension Test: http://yellkey.com/baby How many of these are min heaps?
A. 0 B. 1 C. 2 D. 3 E. 4
8
88
540
6271
888 78 0359
Heap Comprehension Test: http://yellkey.com/present How many of these are min heaps?
A. 0 B. 1 C. 2 D. 3 E. 4
8
88
540
6271
888 78 0359
Incomplete
Lacks min-heap property
What Good Are Heaps?
Heaps lend themselves very naturally to implementation of a priority queue. Hopefully easy question:
● How would you support getSmallest()?
0
51
886
How Do We Add To A Heap?
Challenge: Come up with an algorithm for add(x). ● How would we insert 3?
1
51
6563
? Bonus: Come up with an algorithm for removeSmallest().
Solution: See https://goo.gl/wBKdFQ for an animated demo.
Runtime must be logarithmic.
778
Heap Operations Summary
Given a heap, how do we implement PQ operations?
● getSmallest() – return the item in the root node.
● add(x) – place the new employee in the last position, and promote as high as
possible.
● removeSmallest() – assassinate the president (of the company), promote
the rightmost person in the company to president. Then demote repeatedly, always taking the ‘better’ successor.
See https://goo.gl/wBKdFQ for an animated demo. Remaining question: How would we do all this in Java?
Tree Representations
How do we Represent a Tree in Java?
Approach 1a, 1b and 1c: Create mapping from node to children.
w
xyz
w
z
x
y
public class Tree1A
Tree1A left;
Tree1A middle;
Tree1A right;
…
1a: Fixed-Width Nodes (BSTMap used this approach)
How do we Represent a Tree in Java?
Approach 1a, 1b and 1c: Create mapping from node to children.
w
xyz
w
public class Tree1B
…
z
x
y
1b: Variable-Width Nodes
How do we Represent a Tree in Java?
Approach 1a, 1b and 1c: Create mapping from node to children.
w
xyz
public class Tree1C
Tree1C favoredChild; Tree1C sibling;
…
w
x
y
z
1c: Sibling Tree
How do we Represent a Tree in Java?
Approach 1a, 1b and 1c: Create mapping from node to children.
w
xyz
w
w
z
x
y
z
x
y
1a: Fixed-Width Nodes
1b: Variable-Width Nodes
w
x
y
z
1c: Sibling Tree
How do we Represent a Tree in Java?
Approach 2: Store keys in an array. Store parentIDs in an array. ● Similar to what we did with disjointSets.
w
xyz
public class Tree2
int[] parents;
…
Key[] keys
int[] parents
w
0
x
0
0123
y
0
z
0
0
1e 2v
3b4g5p6y
7adfjmrx
Key[] keys
0 1 2 3 4 int[] parents
k
k
e
v
b
g
p
y
a
d
f
j
m
r
x
5 6 7 8 9 10 11 12 13
0
0
0
1
1
2
2
3
3
4
4
5
5
6
8 9 10
11 12 13
0 1 2 3 4
5 6 7 8 9 10 11 12 13
How do we Represent a Tree in Java?
Approach 3: Store keys in an array. Don’t store structure anywhere.
● To interpret array: Simply assume tree is complete.
● Obviously only works for “complete” trees.
w
xyz
0123
public class Tree3
…
Key[] keys
0
1e 2v
3b4g5p6y
7adfjmrx
Key[] keys
0 1 2 3 4
k
k
e
v
b
g
p
y
a
d
f
j
m
r
x
5 6 7 8 9 10 11 12 13
8 9 10
11 12 13
w
x
y
z
A Deep Look at Approach 3
Challenge: Write the parent(k) method for approach 3.
w
xyz
0123
public void swim(int k) {
if (keys[parent(k)] ≻ keys[k]) {
swap(k, parent(k));
swim(parent(k));
}
}
Key[] keys
w
x
y
z
0
1e 2v
3b4g5p6y
7adfjmrx
Key[] keys
0 1 2 3 4
k
k
e
v
b
g
p
y
a
d
f
j
m
r
x
5 6 7 8 9 10 11 12 13
public class Tree3
…
8 9 10
11 12 13
A Deep Look at Approach 3
Challenge: Write the parent(k) method for approach 3.
w
xyz
0123
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;
}
Key[] keys
kevbgpya
d
f
j
m
r
x
Key[] keys
w
x
y
z
0
1e 2v
3b4g5p6y
7adfjmrx
k
0 1 2 3 4
5 6 7 8 9 10 11 12 13
public class Tree3
…
8 9 10
11 12 13
Tree Representations (Summary)
w
xyz
w
w
z
x
y
z
x
y
1a: Fixed Number of Links (One Per Child)
1b: Array of Child Links
w
w
x
y
z
Key[] keys
int[] parents
Key[] keys
3: Array of Keys
w
x
y
z
0
0
0
0
x
y
z
1c: FirstBorn/Sibling Links
2: Array of Keys, Array of Structure
0123
Approach 3B (book implementation): Leaving One Empty Spot
Approach 3b: Store keys in an array. Offset everything by 1 spot.
● Same as 3, but leave spot 0 empty.
● Makes computation of children/parents “nicer”.
○ leftChild(k) = k*2
○ rightChild(k) = k*2 + 1 ○ parent(k) = k/2
Key[] keys
w
xyz
01234
–
w
x
y
z
1
2e 3v
4b5g6p7y
8adfjmrx
Key[] keys 0 1 2 3 4
k
–
k
e
v
b
g
p
y
a
d
f
j
m
r
x
5 6 7 8 9 10 11 12 13 14
9 10 11
12 13 14
Heap Implementation of a Priority Queue
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)
Notes:
Items with same priority hard to handle.
● Why “priority queue”? Can think of position in tree as its “priority.”
● Heap is log N time AMORTIZED (some resizes, but no big deal).
● BST can have constant getSmallest if you keep a pointer to smallest.
● Heaps handle duplicate priorities much more naturally than BSTs.
● Array based heaps take less memory (very roughly about 1/3rd the memory of representing a tree with approach 1a).
Some Implementation Questions
1. How does a PQ know how to determine which item in a PQ is larger? a. What could we change so that there is a default comparison?
2. What constructors are needed to allow for different orderings?
/** (Min) Priority Queue: Allowing tracking and removal of the
* smallest item in a priority queue. */
public interface MinPQ
/** 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
The Search Problem
Given a stream of data, retrieve information of interest.
● Examples:
○ Website users post to personal page. Serve content only to friends.
○ Given logs for thousands of weather stations, display weather map
for specified date and time.
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
Searching Data Structures:
Stack
PQ
BST
LLRB Hash Table
Linked List ArrayList
Set
Map
List
DisjointSets
Searching Data Structures:
Linked List Resizing Arrays
Separate Chaining HT Linear Probing HT
Heap
Linked List Resizing Arrays
2017 version
Stack
Ordered Array
PQ
BST
LLRB
Set
2-3 Tree
Hash Table
LLRBs
Map
List
DisjointSets
Searching Data Structures:
Heap
Balanced Tree
Chaining HT
Linear Probing HT
Ordered Linked List
LinkedList
Resizing Array
BST (Vanilla)
Red Black
B-Trees (2-3 / 2-3-4)
2016 version
Set
LinkedList
Resizing Array
Map
Heap
Stack
DisjointSets
PQ
List
Chaining HT (lacks order, very odd)
Quick Find Quick Union
Weighted QU
WQUPC
Abstraction often happens in layers!
PQ
Tree
Heap Ordered Tree Array of Buckets
Separate Chaining HT
Approach 1A
Approach 1B
Approach 1C
Approach 2
Approach 3
ArrayList
Bucket
Resizing Array
LinkedList
BST (requires comparable items)
HashSet (weird choice)
Approach 3B
Specialized Searching Data Structures:
List
Stack
Linked List
Queue
Resizing Array (slightly suboptimal due to resizing)
Deque
In Java: java.util.SortedSet
java.util.SortedMap
Set
Sorted Set
BST
2-3 Tree
Map
Sorted Map
RedBlack
PQ
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.
● We’ve covered many of the most fundamental abstract data types, their common implementations, and the tradeoffs thereof.
● We’ll do two more in this class:
○ Tries, graphs.
Citations
Title slide Andre the Giant picture: Unknown source
Friendster screenshot: http://jeremy.zawodny.com/i/friendster_rss.jpg Weather screenshot: weather.com