CSE 326 Data Structures Part 6 Priority Queues AKA Heaps Henry Kautz Autumn 2002 1 Not Quite Queues Consider applications ordering CPU jobs searching for the exit in a maze emergency room admission processing Problems short jobs should go first most promising nodes should be searched first most urgent cases should go first 2 Priority Queue ADT Priority Queue operations create destroy insert deleteMin is empty G 9 insert F 7 E 5 D 100 A 4 B 6 deleteMin C 3 Priority Queue property for two elements in the queue x and y if x has a lower priority value than y x will be deleted before y 3 Applications of the Priority Q Hold jobs for a printer in order of length Store packets on network routers in order of urgency Simulate events Anything greedy 4 Discrete Event Simulation An event is a pair x t where x describes the event and t is time it should occur A discrete event simulator DES maintains a set S of events which it intends to simulate in time order repeat Find and remove x0 t0 from S such that t0 is minimum Do whatever x0 says to do in the process new events x2 t2 xk tk may be generated Insert the new events into S 5 Emergency Room Simulation Patient arrive at time t with injury of criticality C If no patients waiting and a free doctor assign them to doctor and create a future departure event else put patient in the Criticality priority queue Patient departs at time t If someone in Criticality queue pull out most critical and assign to doctor create a future departure event arrive t c patient generator time queue depart t arrive t c depart t assign patient to doctor criticality triage queue 6 Na ve Priority Queue Data Structures Unsorted list insert deleteMin Sorted list insert deleteMin 7 BST Tree Priority Queue Data Structure Regular BST 8 insert 5 deleteMin AVL Tree insert deleteMin 2 11 6 4 10 7 9 12 13 14 Can we do better 8 Binary Heap Priority Q Data Structure Heap order property parent s key is less than children s keys result minimum is always at the top 2 4 Structure property complete tree with fringe nodes packed to the left result depth is always O log n next open location always known 7 11 5 6 9 10 8 12 14 20 How do we find the minimum 9 Nifty Storage Trick Calculations 2 child 2 parent root 4 next free 4 5 7 8 11 6 9 1 9 5 3 6 10 8 7 12 14 20 10 12 11 0 1 2 3 4 5 6 7 8 9 10 11 12 12 2 4 5 7 6 10 8 11 9 12 14 20 10 Nifty Storage Trick Calculations 2 child left 2 node right 2 node 1 parent floor node 2 2 root 1 4 next free length 1 4 5 7 8 11 6 9 1 9 5 3 6 10 8 7 12 14 20 10 12 11 0 1 2 3 4 5 6 7 8 9 10 11 12 12 2 4 5 7 6 10 8 11 9 12 14 20 11 DeleteMin pqueue deleteMin 2 2 20 4 7 11 5 6 9 10 12 14 20 4 8 7 11 5 6 9 10 8 12 14 20 12 Percolate Down 20 4 4 7 5 6 10 20 8 7 11 9 12 14 5 6 10 11 9 12 14 4 4 6 7 8 5 20 11 9 12 14 10 6 8 7 5 12 11 9 20 14 10 8 13 DeleteMin Code Comparable deleteMin x A 1 A 1 A size percolateDown 1 return x Trick to avoid repeatedly copying the value at A 1 runtime percolateDown int hole tmp A hole while 2 hole size left 2 hole right left 1 if right size A right A left target right else target left if A target tmp A hole A target hole target else break Move down A hole tmp 14 Insert pqueue insert 3 2 2 4 7 11 5 6 9 10 12 14 20 4 8 7 11 5 6 9 10 12 14 20 8 3 15 Percolate Up 2 2 4 7 5 6 10 4 8 7 11 9 12 14 20 3 5 6 3 8 11 9 12 14 20 10 2 4 7 3 6 5 11 9 12 14 20 10 8 16 Insert Code void insert Comparable x Efficiency hack we won t actually put x into the heap until we ve located the position it goes in This avoids having to copy it repeatedly during the percolate up int hole size Percolate up for hole 1 x A hole 2 hole hole 2 A hole A hole 2 A hole x runtime 17 Performance of Binary Heap Binary Binary heap heap avg worst case case AVL tree BST tree worst case avg case Insert O log n O 1 percolates 1 6 levels O log n O log n Delete Min O log n O log n O log n O log n In practice binary heaps much simpler to code lower constant factor overhead 18 Changing Priorities In many applications the priority of an object in a priority queue may change over time if a job has been sitting in the printer queue for a long time increase its priority unix renice Must have some separate way of find the position in the queue of the object to change e g a hash table 19 Other Priority Queue Operations decreaseKey Given the position of an object in the queue increase its priority lower its key Fix heap property by increaseKey given the position of an an object in the queue decrease its priority increase its key Fix heap property by remove given the position of an an object in the queue remove it Do increaseKey to infinity then 20 BuildHeap Task Given a set of n keys build a heap all at once Approach 1 Repeatedly perform Insert key Complexity 21 BuildHeap Floyd s Method 12 5 11 3 10 6 9 4 8 1 7 2 pretend it s a heap and fix the heap order property 12 buildHeap for i size 2 i 0 i 5 percolateDown i 11 3 4 10 8 1 6 7 9 2 22 Build this Heap 12 5 11 3 4 10 8 1 2 7 12 5 9 11 3 6 4 1 8 10 2 7 6 12 12 5 2 3 4 1 8 10 6 7 11 9 1 9 2 3 4 5 8 10 6 7 11 9 23 Finally 1 3 2 4 12 5 8 10 6 7 9 11 24 Complexity of Build Heap Note size of a perfect binary tree doubles 1 with each additional layer At most n 4 percolate down 1 level at most n 8 percolate down 2 levels at most n 16 percolate down 3 levels log n n n n …
View Full Document
Unlocking...