Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·February 27, 2012 5:24:08 AMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E2.4 PRIORITY QUEUES‣API‣elementary implementations‣binary heaps‣heapsort‣event-driven simulation‣API‣elementary implementations‣binary heaps‣heapsort‣event-driven simulation23Priority queueCollections. Insert and delete items. Which item to delete?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.P 1 P PQ 2 P Q P QE 3 P Q E E P Q Q 2 P E E PX 3 P E X E P XA 4 P E X A A E P XM 5 P E X A M A E M P X X 4 P E M A A E M PP 5 P E M A P A E M P PL 6 P E M A P L A E L M P PE 7 P E M A P L E A E E L M P P P 6 E M A P L E A E E L M P insertinsertinsertremove maxinsertinsertinsertremove maxinsertinsertinsertremove maxoperation argumentreturnvaluecontents(unordered)contents(ordered)sizeA sequence of operations on a priority queue4Priority queue APIRequirement. Generic items are Comparable. public class MaxPQ<Key extends Comparable<Key>> public class MaxPQ<Key extends Comparable<Key>> public class MaxPQ<Key extends Comparable<Key>>MaxPQ()create an empty priority queueMaxPQ(Key[] a)create a priority queue with given keysvoidinsert(Key v)insert a key into the priority queueKeydelMax()return and remove the largest keybooleanisEmpty()is the priority queue empty?Keymax()return the largest keyintsize()number of entries in the priority queueKey must be Comparable(bounded type parameter)5Priority queue applications•Event-driven simulation. [customers in a line, colliding particles]•Numerical computation. [reducing roundoff error]•Data compression. [Huffman codes]•Graph searching. [Dijkstra's algorithm, Prim's algorithm]•Computational number theory. [sum of powers]•Artificial intelligence. [A* search]•Statistics. [maintain largest M values in a sequence]•Operating systems. [load balancing, interrupt handling]•Discrete optimization. [bin packing, scheduling]•Spam filtering. [Bayesian spam filter]Generalizes: stack, queue, randomized queue.Challenge. Find the largest M items in a stream of N items (N huge, M large).•Fraud detection: isolate $$ transactions.•File maintenance: find biggest files or directories.Constraint. Not enough memory to store N items.6Priority queue client example% more tinyBatch.txtTuring 6/17/1990 644.08vonNeumann 3/26/2002 4121.85Dijkstra 8/22/2007 2678.40vonNeumann 1/11/1999 4409.74Dijkstra 11/18/1995 837.42Hoare 5/10/1993 3229.27vonNeumann 2/12/1994 4732.35Hoare 8/18/1992 4381.21Turing 1/11/2002 66.10Thompson 2/27/2000 4747.08Turing 2/11/1991 2156.86Hoare 8/12/2003 1025.70vonNeumann 10/13/1993 2520.97Dijkstra 9/10/2000 708.95Turing 10/12/1993 3532.36Hoare 2/10/2005 4050.20% java TopM 5 < tinyBatch.txtThompson 2/27/2000 4747.08 vonNeumann 2/12/1994 4732.35vonNeumann 1/11/1999 4409.74Hoare 8/18/1992 4381.21vonNeumann 3/26/2002 4121.85sort keyChallenge. Find the largest M items in a stream of N items (N huge, M large).7Priority queue client exampleimplementationtimespacesortN log NNelementary PQM NMbinary heapN log MMbest in theoryNMorder of growth of finding the largest M in a stream of N itemsMinPQ<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();}pq containslargest M itemsuse a min-oriented pqTransaction datatype is Comparable(ordered by $$)‣API‣elementary implementations‣binary heaps‣heapsort‣event-driven simulation89Priority queue: unordered and ordered array implementationP 1 P PQ 2 P Q P QE 3 P Q E E P Q Q 2 P E E PX 3 P E X E P XA 4 P E X A A E P XM 5 P E X A M A E M P X X 4 P E M A A E M PP 5 P E M A P A E M P PL 6 P E M A P L A E L M P PE 7 P E M A P L E A E E L M P P P 6 E M A P L E A E E L M P insertinsertinsertremove maxinsertinsertinsertremove maxinsertinsertinsertremove maxoperation argumentreturnvaluecontents(unordered)contents(ordered)sizeA sequence of operations on a priority queue10Priority queue: unordered array implementationpublic 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]; }}no genericarray creationless() and exch()similar to sorting methodsnull out entryto prevent loitering11Priority queue elementary implementationsChallenge. Implement all operations efficiently.implementationinsertdel maxmaxunordered array1NNordered arrayN11goallog Nlog Nlog Norder-of-growth of running time for priority queue with N items‣API‣elementary implementations‣binary heaps‣heapsort‣event-driven simulation12Binary tree. Empty or node with links to left and right binary trees.Complete tree. Perfectly balanced, except for bottom level.Property. Height of complete tree with N nodes is ⎣lg N⎦.Pf. Height only increases when N is a power of 2.13Binary treecomplete tree with N = 16 nodes (height = 4)14A complete binary tree in nature15Binary heap representationsBinary heap. Array representation of a heap-ordered complete
View Full Document
Unlocking...