DOC PREVIEW
Princeton COS 226 - Priority Queues

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Princeton COS 226 - Priority Queues

Documents in this Course
QUICKSORT

QUICKSORT

14 pages

QUICKSORT

QUICKSORT

55 pages

STRINGS

STRINGS

69 pages

Lecture

Lecture

4 pages

STRINGS

STRINGS

18 pages

Hashing

Hashing

7 pages

MERGESORT

MERGESORT

14 pages

Quicksort

Quicksort

12 pages

Strings

Strings

10 pages

Overview

Overview

15 pages

Hashing

Hashing

13 pages

Mergesort

Mergesort

15 pages

Tries

Tries

13 pages

Final

Final

12 pages

Final

Final

12 pages

Mergesort

Mergesort

13 pages

Final

Final

10 pages

Load more
Download Priority Queues
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Priority Queues and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Priority Queues 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?