Pre-Announcements
Justin: Alpha Kappa Psi Blockchain Event, next Wednesday in Chevron Auditorium
Fliers up front if you want to do this thing.
Announcements
Midterm 2:
�
CS61B
Lecture 24: Priority Queues and Heaps
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();
}
Usage Example: Unharmonious Texts
Imagine that you’re part of Grand Leader’s Information Compliance and Happiness Enhancement (GLICHE) team.
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
Potentially uses a huge amount of memory Θ(N), where N is number of texts.
public List<String> unharmoniousTexts(Sniffer sniffer, int M) {
ArrayList<String> allMessages = new ArrayList<String>();
for (Timer timer = new Timer(); timer.hours() < 24; ) {
allMessages.add(sniffer.getNextMessage());
}
Comparator<String> cmptr = new HarmoniousnessComparator();
Collections.sort(allMessages, cmptr, Collections.reverseOrder());
return allMessages.sublist(0, M);
}
MinPQ<String> unharmoniousTexts = new HeapMinPQ<Transaction>(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 do explicit comparisons).
public List<String> unharmoniousTexts(Sniffer sniffer, int M) {
Comparator<String> cmptr = new HarmoniousnessComparator();
MinPQ<String> unharmoniousTexts = new HeapMinPQ<Transaction>(cmptr);
for (Timer timer = new Timer(); timer.hours() < 24; ) {
unharmoniousTexts.add(sniffer.getNextMessage());
if (unharmoniousTexts.size() > M)
{ unharmoniousTexts.removeSmallest(); }
}
ArrayList<String> textlist = new ArrayList<String>();
while (unharmoniousTexts.size() > 0) {
textlist.add(unharmoniousTexts.removeSmallest());
}
return textlist;
}
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
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.
0
5
8
0
8
1
2
6
5
8
0
8
1
6
5
8
0
8
1
2
5
4
0
8
1
6
Incomplete
Lacks min-heap property
Heap Comprehension Test: http://yellkey.com/baby
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: http://yellkey.com/present
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
How Do We Add To A Heap?
Challenge: Come up with an algorithm for add(x).
Runtime must be logarithmic.
Bonus: Come up with an algorithm for removeSmallest().
Solution: See https://goo.gl/wBKdFQ for an animated demo.
5
5
1
6
1
3
6
7
7
8
?
Heap Operations Summary
Given a heap, how do we implement PQ operations?
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
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
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
-
In next week’s lab, you’ll implement a MinPQ.
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
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 |
Searching Data Structures:
PQ
List
Set
Map
DisjointSets
Stack
Hash Table
BST
LLRB
2-3 Tree
Searching Data Structures:
PQ
List
Set
Map
DisjointSets
Stack
BST
2-3 Tree
LLRBs
Separate Chaining HT
Linear Probing HT
Linked List
Resizing Arrays
Linked List
Resizing Arrays
Ordered Array
LLRB
Hash Table
Heap
2017 version
Searching Data Structures:
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
2016 version
PQ
Heap Ordered Tree
External Chaining HT
Array of Buckets
Abstraction often happens in layers!
Bucket
ArrayList
Resizing Array
LinkedList
BST (requires comparable items)
Tree
Approach 1A
Approach 1B
Approach 1C
Approach 2
Approach 3
Approach 3B
ArrayMap (lab 9)
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.
Citations
Title slide Andre the Giant picture: Unknown source
Friendster screenshot: http://jeremy.zawodny.com/i/friendster_rss.jpg
�Weather screenshot: weather.com