Priority Queues
- Stack: Remove the item most recently added
- Queue: Remove the item least recently added
- Randomized queue: Remove a random item
- Priority queue: Remove the largest (or smallest) item
APIs and implementations
Requirement: Generic items are Comparable
public class MaxPQ<Key extends Comparable<Key>>
MaxPQ()
void insert (Key y)
Key delMax()
boolean isEmpty()
Key max()
int size()
Find the largest M items in a stream of N items. But no enough memory to store N items.
MinPQ<Transaction> pq = new MinPQ<Transaction>();
while (StdIn.hasNextLine())
{
String line = StdIn.readLine();
Transaction item = new Transaction(line);
pq.insert(item);
if (pq.size() > M)
pq.delMin();
}
| implementation | time | space |
|---|---|---|
| sort | N log N | N |
| elementary PQ | M N | M |
| binary heap | N log M | M |
| best in theory | N | M |
unordered implementation
public class UnorderedMaxPQ<Key extends Comparable<Key>>
{
private Key[] pq; // pq[i] = ith element on pq
private int N; // number of elements on pq
public UnorderedMaxPQ(int capacity)
{ pq = (Key[]) new Comparable[capacity]; }
public boolean isEmpty()
{ return N == 0; }
public void insert(Key x)
{ pq[N++] = x; }
public Key delMax()
{
int max = 0;
for (int i = 1; i < N; i++)
if (less(max, i)) max = i;
exch(max, N-1);
return pq[--N];
}
}
| implementation | insert | del max | max |
|---|---|---|---|
| unordered | 1 | N | N |
| ordered | N | 1 | 1 |
| goal | log N | log N | log N |
binary heaps
Complete binary tree:
- Binary tree: empty or node with links to left and right binary trees
- Complete tree: perfect balanced, except for bottom level
- height of complete tree with N nodes is
Array representation:
- parent’s key is no smaller than children’s keys
- indices start at 1
- take nodes in level order
- no explicit links needed
- largest key is
a[1], which is root of binary tree - parent of node k is at
k/2 - children of node at k are at
2kand2k+1
promotion in a heap
To avoid having larger child’s key than its parent’s key
- exchange key in child with key in parent
- repeat until heap order restored
insertion in a heap:
- insert: add node at end, then swim it up
- cost: at most compares
private void swim(int k)
{
while (k > 1 && less(k/2, k))
{
exch(k/2,k);
k = k/2;
}
}
// insertion in a heap
public void insert(Key x)
{
pq[++N] = x;
swim[N];
}
demotion in a heap
Parent’s key becomes smaller than one or both of its children’s
- exchange key in parent with key in larger child
- repeat until heap order restored
private void sink(int k)
{
while (2*k <= N)
{
int j = 2*k;
if (j < N && less(j,j+1)) j++;
if (!less(k, j)) break;
exch(k,j);
k = j;
}
}
// del max
public Key delMax()
{
Key max = pq[1];
exch(1,N--);
sink(1);
pq[N+1] = null; // prevent loitering
return max;
}
full implementation
public class MaxPQ<Key extends Comparable<Key>>
{
private Key[] pq;
private int N;
public MaxPQ(int capacity)
{ pq = (Key[]) new Comparable[capacity+1]; }
public boolean isEmpty()
{ return N == 0; }
public void insert(Key key)
public Key delMax()
{ /* see previous code */ }
private void swim(int k)
private void sink(int k)
{ /* see previous code */ }
private boolean less(int i, int j)
{ return pq[i].compareTo(pq[j]) < 0; }
private void exch(int i, int j)
{ Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }
}
considerations
- immutability of keys
- client does not change keys while they’re on the PQ
- best practice: use immutable keys
- underflow and overflow
- throw exception if deleting from empty PQ
- add no-arg constructor and use resizing array
- minumum-oriented priority queue
- replace
less()withgreater() - implement
greater()
- replace
- other operations (use
sink()andswim())- remove an arbitrary item
- change the priority of an item
immutability
Data type: set of values and operations on those values
immutable data type: can’t change the data type value once created
immutable: string, integer, double, color, vector,…
mutable: stringbuilder, stack, counter, java array
// immutability, use private, final
public final class Vector {
private final int N;
private final double[] data;
public Vector(double[] data) {
this.N = data.length;
this.data = new double[N];
for (int i = 0; i < N; i++)
this.data[i] = data[i];
}
…
}
heapsort
plan for the in-place sort
- create max-heap with all N keys
- repeatedly remove the maximum key
- start with array of keys in arbitrary order
- build a max-heap (in place)
- sorted result (in place)
// build heap using bottom-up method
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
// remove max
while (N>1)
{
exch(a,1, N--);
sink(a, 1, N);
}
complete implementation
public class Heap
{
public static void sort(Comparable[] a)
{
int N = a.length;
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
while (N > 1)
{
exch(a, 1, N);
sink(a, 1, --N);
}
}
private static void sink(Comparable[] a, int k, int N)
{ /* as before */ }
private static boolean less(Comparable[] a, int i, int j)
{ /* as before */ }
private static void exch(Comparable[] a, int i, int j)
{ /* as before */ }
}
analysis
- Heap construction uses compares and exchanges
- Heapsort uses compares and exchanges
In-place sorting algorithm with worst-case
Bottom line: heapsort is optimal for both time and space but:
- inner loop longer than quicksort’s
- makes poor use of cache memory
- not stable
event-driven simulation
dynamics of hard discs
goal: simulate the motion of N moving particles that behave according to the law of elastic collision
elementary symbol tables
symbol table api
symbol tables
key-value pair abstraction
- insert a value with specified key
- given a key, search for the corresponding value
public class ST<Key, Value>
{
ST() create a symbol table
void put(Key key, Value val) //put key-value pair into the table
// (remove key from table if value is null)
Value get(Key key) //value paired with key
// (null if key is absent)
void delete(Key key) // remove key (and its value) from table
boolean contains(Key key) //is there a value paired with //key?
boolean isEmpty() // is the table empty?
int size() // number of key-value pairs in the table
Iterable<Key> keys() // all the keys in the table
}
conventions
- values are not
null - method
get()returnsnullif key not present - method
put()overwrites old value with new value
keys and values
value type: any generic type
key type: several natural assumptions
- keys are
Comparable, usecompareTo() - keys are any generic type, use
equals()to test equality - keys are any generic type, use
hashCode()to scramble key
elementary implementations
sequential search in a linked list
data structure: maintain an (unordered) linked list of key-value pairs
search: scan through all keys until find a match
insert: scan trhough all keys until find a match; if no match add to front
equals() is the key interface
binary search in an ordered array
maintain an ordered array of key-value pairs
compareTo() is the key interface
ordered operations
public class ST<Key extends Comparable<Key>, Value>
{
ST() // create an ordered symbol table
void put(Key key, Value val) // put key-value pair into // the table
// (remove key from table if value is null)
Value get(Key key) // value paired with key
// (null if key is absent)
void delete(Key key) // remove key (and its value) from // table
boolean contains(Key key) // is there a value paired with // key?
boolean isEmpty() // is the table empty?
int size() // number of key-value pairs
Key min() // smallest key
Key max() // largest key
Key floor(Key key) // largest key less than or equal to // key
Key ceiling(Key key) // smallest key greater than or //equal to key
int rank(Key key) // number of keys less than key
Key select(int k) // key of rank k
void deleteMin() // delete smallest key
void deleteMax() // delete largest key
int size(Key lo, Key hi) // number of keys in [lo..hi]
Iterable<Key> keys(Key lo, Key hi) // keys in [lo..hi], // in sorted order
Iterable<Key> keys() // all keys in the table, in sorted // order
}
binary search trees
Definition: A BST is a binary tree in symmetric order.
A BST is either:
- empty
- two disjoint binary trees (left and right)
symmetric order: each node has a key, and every node’s key is
- larger than all keys in its left subtree
- smaller than all keys in its right subtree
In java, A BST is a reference to a root node.
A node is comprised of four fields:
- A key and a value
- A reference to the left and right subtree
search and insert
compare keys: if less, go left; if greater, go right; if null, insert.
private class Node
{
private Key key;
private Value val;
private Node left, right;
public Node(Key key, Value val)
{
this.key = key;
this.val = val;
}
}
search:
public Value get(Key key)
{
Node x = root;
while (x != null)
{
int cmp = key.compareTo(x.key);
if (cmp < 0) x = x.left;
else if (cmp > 0) x = x.right;
else if (cmp == 0) return x.val;
}
return null;
}
put:
public void put(Key key, Value val)
{ root = put(root, key, val); }
private Node put(Node x, Key key, Value val)
{
if (x == null) return new Node(key, val);
int cmp = key.compareTo(x.key);
if (cmp < 0)
x.left = put(x.left, key, val);
else if (cmp > 0)
x.right = put(x.right, key, val);
else if (cmp == 0)
x.val = val;
return x;
}
ordered operations in BSTs
find minimum and maximum
find floor and ceiling
floor:
public Key floor(Key key)
{
Node x = floor(root, key);
if (x == null) return null;
return x.key;
}
private Node floor(Node x, Key key)
{
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp == 0) return x;
if (cmp < 0) return floor(x.left, key);
Node t = floor(x.right, key);
if (t != null) return t;
else return x;
}
rank (how many keys < k):
public int rank(Key key)
{ return rank(key, root); }
private int rank(Key key, Node x)
{
if (x == null) return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0) return rank(key, x.left);
else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
else if (cmp == 0) return size(x.left);
}
deletions in BSTs
unsatisfactory to remove a node with a given key:
- set its value to null
- leave key in tree to guide searchs (but don’t consider it equal in search)
deleteMin() and deleteMax() are easy.
Hibbard deletion
Unsatisfactory solution: not symmetric, leading to height
If the node to be deleted has no child or only one child, deleting is easy.
node with 2 children:
- find successor x of t (x has no left child, in the right tree of t)
- delete the minimum x in t’s right tree
- put x in t’s spot
public void delete(Key key)
{ root = delete(root, key); }
private Node delete(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);
else if (cmp > 0) x.right = delete(x.right, key);
else {
if (x.right == null) return x.left;
if (x.left == null) return x.right;
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.count = size(x.left) + size(x.right) + 1;
return x;
}
