Question? Leave a message!




PRIORITY QUEUES

PRIORITY QUEUES
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 2.4 PRIORITY QUEUES API and elementary implementations ‣ binary heaps ‣ heapsort ‣ Algorithms FOUR TH EDITION event-driven simulation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu Last updated on 3/29/17 9:01 AM2.4 PRIORITY QUEUES API and elementary implementations ‣ binary heaps ‣ heapsort ‣ Algorithms event-driven simulation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduCollections A collection is a data type that stores a group of items. data type core operations data structure PUSH, POP stack linked list, resizing array ENQUEUE, DEQUEUE queue linked list, resizing array INSERT, DELETE-MAX priority queue binary heap PUT, GET, DELETE symbol table binary search tree, hash table ADD, CONTAINS, DELETE set binary search tree, hash table “ Show me your code and conceal your data structures, and I shall continue to be mystified. Show me your data structures, and I won't usually need your code; it'll be obvious.” — Fred Brooks 3Priority queue Collections. 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. return contents contents Generalizes: stack, queue, randomized queue. operation argument size value (unordered) (ordered) insert P 1 P P insert Q 2 P Q P Q insert E 3 P Q E E P Q remove max Q 2 P E E P insert X 3 P E X E P X insert A 4 P E X A A E P X insert M 5 P E X A M A E M P X remove max X 4 P E M A A E M P insert P 5 P E M A P A E M P P insert L 6 P E M A P L A E L M P P insert E 7 P E M A P L E A E E L M P P remove max P 6 E M A P L E A E E L M P 4 A sequence of operations on a priority queuePriority queue API Requirement. Items are generic; they must also be Comparable. 
 Key must be Comparable 
 (bounded type parameter) 
 public class MaxPQKey extends ComparableKey 
 MaxPQ() create an empty priority queue 
 MaxPQ(Key a) 
 create a priority queue with given keys 
 insert(Key v) void insert a key into the priority queue 
 delMax() Key return and remove a largest key 
 isEmpty() boolean is the priority queue empty? 
 
 max() Key return a largest key 
 size() int number of entries in the priority queue 
 
 Note. Duplicate keys allowed; delMax() picks any maximum key. 5Priority queue: applications Event-driven simulation. customers in a line, colliding particles Numerical computation. reducing roundoff error Discrete optimization. bin packing, scheduling Artificial intelligence. A search Computer networks. web cache Operating systems. load balancing, interrupt handling Data compression. Huffman codes Graph searching. Dijkstra's algorithm, Prim's algorithm Number theory. sum of powers Spam filtering. Bayesian spam filter Statistics. online median in data stream 6Priority queue: client example Challenge. Find the largest m items in a stream of n items. Fraud detection: isolate transactions. n huge, m large NSA monitoring: flag most suspicious documents. 
 Constraint. Not enough memory to store n items. Transaction data
 type is Comparable (ordered by ) MinPQTransaction pq = new MinPQTransaction(); while (StdIn.hasNextLine()) use a min-oriented pq String line = StdIn.readLine(); Transaction transaction = new Transaction(line); pq.insert(transaction); if (pq.size() m) pq now contains
 pq.delMin(); largest m items 7Priority queue: client example Challenge. Find the largest m items in a stream of n items. implementation time space sort n log n n elementary PQ m n m binary heap n log m m best in theory n m order of growth of finding the largest m in a stream of n items 8Priority queue: unordered and ordered array implementation r re et tur urn n c cont onte ents nts c cont onte ents nts o op pe er rat ation ion ar argume gument nt siz size e v value alue (unor (unorde der re ed) d) (or (orde der re ed) d) ins inse er rt t P 1 P 1 P P P P insert insert Q 2 P Q 2 P Q Q P P QQ ins inse er rt t E 3 P Q E E P Q E 3 P Q E E P Q r re emo mov ve max e max QQ 2 P E E P 2 P E E P insert insert X 3 P E X E P X X 3 P E X E P X ins inse er rt t A 4 P E X A A E P X A 4 P E X A A E P X insert insert M 5 P E X A M 5 P E X A M M A E A E MM P X P X remove max remove max X 4 P E M A A E M P X 4 P E M A A E M P insert insert P 5 P E M A P 5 P E M A P P A E M P A E M P PP insert insert L 6 P E M A P L A E L M P P L 6 P E M A P L A E L M P P ins inse er rt t E 7 P E M A P L E A E E L M P P E 7 P E M A P L E A E E L M P P remove max remove max PP 6 E M A P L E A E E L M P 6 E M A P L E A E E L M P A sequence of operations on a priority queue A sequence of operations on a priority queue 9Priority queue: implementations cost summary Challenge. Implement all operations efficiently. 
 
 
 
 implementation insert del max max 
 unordered array 1 n n 
 
 n 1 1 ordered array 
 goal log n log n log n 
 
 order of growth of running time for priority queue with n items 
 
 
 
 Solution. Partially-ordered array. 102.4 PRIORITY QUEUES API and elementary implementations ‣ binary heaps ‣ heapsort ‣ Algorithms event-driven simulation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduComplete binary tree Binary tree. Empty or node with links to left and right binary trees. Complete tree. Perfectly balanced, except for bottom level. 
 
 
 
 
 
 
 
 complete binary tree with n = 16 nodes (height = 4) 
 
 Property. Height of complete binary tree with n nodes is ⎣lg n⎦. Pf. Height increases only when n is a power of 2. 12A complete binary tree in nature 13Binary heap: representation Binary heap. Array representation of a heap-ordered complete binary tree. 
 Heap-ordered binary tree. Keys in nodes. Parent's key no smaller than
 children's keys. i i 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 ai - T S R P N O A E I H G ai - T S R P N O A E I H G 
 TT Array representation. S R S R Indices start at 1. P N O A P N O A Take nodes in level order. No explicit links needed E I H G E I H G 11 TT 33 22 SS RR 66 77 55 44 PP NN OO AA 10 10 11 11 88 99 EE II HH GG Heap r Heap repr epresen esenta tations tions 14Binary heap: properties Proposition. Largest key is a1, which is root of binary tree. 
 Proposition. Can use array indices to move through tree. Parent of node at k is at k/2. Children of node at k are at 2k and 2k+1. i 0 1 2 3 4 5 6 7 8 9 10 11 ai - T S R P N O A E I H G T S R P N O A E I H G 1 T 3 2 S R 6 7 5 4 P N O A 10 11 8 9 E I H G Heap representations 15Binary heap demo Insert. Add node at end, then swim it up. Remove the maximum. Exchange root with node at end, then sink it down. heap ordered T P R N H O A E I G T P R N H O A E I G 16Binary heap demo Insert. Add node at end, then swim it up. Remove the maximum. Exchange root with node at end, then sink it down. heap ordered S R O N G A P E I H S R O N P G A E I H 17Binary heap: promotion Scenario. A key becomes larger than its parent's key. 
 To eliminate the violation: Exchange key in child with key in parent. Repeat until heap order restored. S 
 P R private void swim(int k) 
 5 N T O A 
 violates heap order while (k 1 && less(k/2, k)) E I H G (larger key than parent) 
 1 exch(k, k/2); 
 T k = k/2; 2 S R 
 parent of node at k is at k/2 5 N P O A 
 E I H G 
 Bottom-up reheapify (swim) 
 
 Peter principle. Node promoted to level of incompetence. 18Binary heap: insertion Insert. Add node at end, then swim it up. Cost. At most 1 + lg n compares. insert remove the maximum key to remove T T P R S R N H O A N P O A exchange key key to insert E I G S E I G H with root public void insert(Key x) violates T H heap order pq++n = x; P R S R swim(n); N H O A N P O A remove node add key to heap E I G S E I G T from heap violates heap order T S swim up S R P R sink down N P O A N H O A E I G H E I G Heap operations 19Binary heap: demotion Scenario. A key becomes smaller than one (or both) of its children's. 
 why not smaller child? To eliminate the violation: Exchange key in parent with key in larger child. Repeat until heap order restored. 
 violates heap order private void sink(int k) (smaller than a child) T 
 2 children of node at k H R while (2k = n) 
 are 2k and 2k+1 5 P S O A 
 E I N G int j = 2k; 
 if (j n && less(j, j+1)) j++; T if (less(k, j)) break; 2 
 S R exch(k, j); 5 P N O A 
 k = j; 10 E I H G 
 Top-down reheapify (sink) 
 
 Power struggle. Better subordinate promoted. 20