Princeton University • COS 226 • Algorithms and Data Structures • Spring 2004 • Kevin Wayne • http://www.Princeton.EDU/~cos226Priority QueuesReference: Chapter 6, Algorithms in Java, 3rdEdition, Robert Sedgewick.Priority Queue ADTBinary heapsHeapsort2Client, Implementation, InterfaceSeparate interface and implementation so as to:n Build layers of abstraction.n Reuse software.n Ex: stack, queue, symbol table.Interface: description of data type, basic operations.Client: program using operations defined in interface.Implementation: actual code implementing operations.Benefits.n Client can't know details of implementation, so has many implementation from which to choose.n Implementation can't know details of client needs, so many clients can re-use the same implementation.n Performance: use optimized implementation where it matters.n Design: creates modular, re-usable libraries.3Abstract Data TypesIdealized scenario.n Design general-purpose ADT useful for many clients.n Develop efficient implementation of all ADT functions.n Each ADT provides a new level of abstraction.Total cost depends on:n ADT implementation.n Client usage pattern.ADTclientsalgorithmsmight need different implementationsfor different clientsalgorithms and data structures4Priority QueuesRecords with keys (priorities) that can be compared.Basic operations.n Insert.n Remove largest.n Create.n Test if empty.n Copy.n Destroy.PQ opsgenericADT opsnot needed for one-time use, but criticalin large systems when writing in C or C++5Priority Queue ApplicationsApplications.n Event-driven simulation. customers in a line, colliding particlesn Numerical computation. reducing roundoff errorn Data compression. Huffman codesn Graph searching. shortest path, MSTn Computational number theory. sum of powersn Artificial intelligence. A* searchn Statistics. maintain largest M values in a sequencen Operating systems. task scheduling, interrupt handlingn Discrete optimization. bin packing heuristicsn Spam filtering. Bayesian spam filter6Priority Queue Client ExampleProblem: Find the largest M of a stream of N elements.Ex 1: Fraud detection - isolate $$ transactions.Ex 2: File maintenance – find biggest files or directories.Possible constraint: may not have enough memory to store N elements.Solution: Use a priority queue.Ex: top 10,000 in a stream of 1 billion.n Not possible without good algorithm.PQ pq = new PQ();while(!StdIn.isEmpty()) {String s = StdIn.readString();pq.insert(s);if (pq.size() > M)pq.delMax();}while (!pq.isEmpty())System.out.println(pq.delMax());sortOperationelementary PQbinary heapbest in theoryNspaceMMMN lg Ntime M NN lg MN7Unordered Array Priority Queue Implementationpublic class PQ {private Comparable[] pq; // pq[i] = ith elementprivate int N; // number of elements on PQpublic PQ() { pq = new Comparable[8]; }public boolean isEmpty() { return N == 0; }public void insert(Comparable x) {pq[N++] = x;}public Comparable delMax() {int max = 0;for (int i = 1; i < N; i++)if (less(pq[max], pq[i])) max = i;exch(pq, max, N-1);return pq[--N];}}constructorremove and return max element from PQis the PQ empty?insert element x into PQ8Implementation DetailsWhat if I don't know the max capacity of the PQ ahead of time?n Double the size of the array as needed.n Add following code to insert before updating array.Memory leak.n Garbage collector only reclaims memory if there is no outstanding reference to it.n When deleting element N-1 from the priority queue, set:if (N >= pq.length) {Comparable[] temp = new Comparable[2*N];for (int i = 0; i < N; i++)temp[i] = pq[i];pq = temp;}pq[N-1]=null;9Priority Queues Implementation Cost SummaryCan we implement all operations efficiently?ordered arrayOperationordered listunordered arrayunordered list1Remove Max1NN1Find Max1NNNInsert N11Worst-Case Asymptotic costs for PQ with N items12HeapHeap: Array representation of a heap-ordered complete binary tree.Binary tree.n null orn Node with links to left andright trees.Heap-ordered binary tree.n Keys in nodes.n No smaller than children’s keys.Array representation.n Take nodes in level order.n No explicit links needed sincetree is complete.13Heap PropertiesLargest key is at root.Use array indices to move through tree.n Note: indices start at 1.n Parent of node at k is at k/2.n Children of node at k are at 2k and 2k+1.Length of path in N-node heap is at most ~ lg N.n n levels when 2n ≤ N < 2n + 1.n n ≤ lg N < n+1.n ~ lg N levels.14Promotion (Bubbling Up) In a HeapSuppose that exactly one node is bigger than its parent.To eliminate the violation:n Exchange with its parent.n Repeat until heap order restored.Peter principle: node promoted to levelof incompetence.private void swim(int k) {while (k > 1 && less(k/2, k)) {exch(k, k/2);k = k/2;}}parent of node at k is at k/215Demoting (Sifting Down) In a HeapSuppose that exactly one node is smaller than a child.To eliminate the violation:n Exchange with larger child.n Repeat until heap order restored.Power struggle: better subordinate promoted.private void sink(int k, int N) {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;}}children of nodeat k are 2k and 2k+116Insert and Delete MaxInsert. Add node at end, then promote.Remove largest. Exchange root withnode at end, then sift down.public Comparable delMax() {exch(1, N);sink(1, N-1);return pq[N--];}public void insert(Comparable x) {pq[++N]=x;swim(N);}17Expansion: double size of array as needed.Memory leak: when deleting element N, set pq[N] = null.public class PQ {private Comparable[] pq;private int N;public PQ() {}public boolean isEmpty() {}public int size() {}public void insert(Comparable x) { }public Comparable delMax() {}private void swim(int k) {}private void sink(int k, int N) {}private boolean less(int i, int j) { }private void exch(int i, int j) { }}Heap Based Priority Queue in Javaexactly as in array-based PQhelper functionssame as array-based PQ, but allocate one extra element in arrayheap helper functionsPQ ops18Priority Queues Implementation Cost SummaryHopeless challenge: get all ops O(1).ordered arrayOperationordered listunordered arrayunordered listheap1Remove Max1NNlg N1Find Max1NN1NInsert N11lg NWorst-Case Asymptotic costs for PQ with N items19Digression: HeapsortFirst pass: build heap.n Add item to heap at each iteration, then sift up.n Or can use faster bottom-up method; see book.Second pass: sort.n Remove maximum at each
View Full Document