CSE 326 Data Structures Part 6: Priority Queues, AKA HeapsNot Quite QueuesPriority Queue ADTApplications of the Priority QDiscrete Event SimulationEmergency Room SimulationNaïve Priority Queue Data StructuresBST Tree Priority Queue Data StructureBinary Heap Priority Q Data StructureNifty Storage TrickSlide 11DeleteMinPercolate DownDeleteMin CodeInsertPercolate UpInsert CodePerformance of Binary HeapChanging PrioritiesOther Priority Queue OperationsBuildHeapBuildHeap Floyd’s MethodBuild(this)HeapFinally…Complexity of Build HeapHeap SortProperties of Heap SortThinking about HeapsSolution: d-HeapsComing UpNew Operation: MergeBinomial QueuesBuilding a Binomial TreeSlide 34Slide 35Slide 36Slide 37Slide 38Slide 39Why Binomial?Slide 41Definition of Binomial QueuesBinomial Queue PropertiesBinomial Queues: MergeExample: Binomial Queue MergeSlide 46Slide 47Slide 48Slide 49Slide 50Binomial Queues: Merge and InsertSlide 52Insert 1,2,…,7Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Binomial Queues: DeleteMinSlide 62Slide 63MergeSlide 65Slide 66Slide 67Implementation of Binomial QueuesEfficient BuildHeap for Binomial QueuesOther Mergeable Priority Queues: Leftist and Skew HeapsSlide 71Leftist HeapsIdea: Hang a New TreeSlide 74Slide 75Slide 76Problem?Slide 78Random Definition: Null Path LengthLeftist Heap PropertiesLeftist tree examplesRight Path in a Leftist Tree is ShortMerging Two Leftist HeapsMerge ContinuedOperations on Leftist HeapsExampleSewing Up the ExampleSlide 88Skew HeapsMerging Two Skew HeapsSlide 91Skew Heap CodeComparing HeapsSummary of Heap ADT Analysis1CSE 326 Data StructuresPart 6:Priority Queues, AKA HeapsHenry KautzAutumn 20022Not 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 first3Priority Queue ADT•Priority Queue operations–create–destroy–insert–deleteMin–is_empty•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 yF(7) E(5) D(100) A(4) B(6)insertdeleteMinG(9) C(3)4Applications 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 greedy5Discrete 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 orderrepeat {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; }6Emergency 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 eventtimequeuearrive(t,c)criticality(triage)queueassignpatient todoctorpatientgeneratordepart(t)depart(t)arrive(t,c)7Naïve Priority Queue Data Structures•Unsorted list:–insert:–deleteMin:•Sorted list:–insert:–deleteMin:8BST Tree Priority Queue Data Structure4121062115814137 9•Regular BST:–insert:–deleteMin:•AVL Tree:–insert:–deleteMin:Can we do better?9Binary Heap Priority Q Data Structure20141291181067542•Heap-order property–parent’s key is less than children’s keys–result: minimum is always at the top•Structure property–complete tree with fringe nodes packed to the left–result: depth is always O(log n); next open location always knownHow do we find the minimum?10201412911810675422 4 5 7 6 10 8 11 9 12 14 20121 2 3 4 5 6 7 8 9 10 11 1212 345 678910 1112Nifty Storage Trick•Calculations:–child:–parent:–root:–next free:011201412911810675422 4 5 7 6 10 8 11 9 12 14 20121 2 3 4 5 6 7 8 9 10 11 1212 345 678910 1112Nifty Storage Trick•Calculations:–child: left = 2*node right=2*node+1–parent: floor(node/2)–root: 1–next free: length+1012DeleteMin201412911810675420220141291181067542pqueue.deleteMin()13Percolate Down141291181067542014129118106752041412911810207564142091181012756414DeleteMin CodeComparable deleteMin(){ x = A[1]; A[1]=A[size--]; percolateDown(1); return x;}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; } A[hole] = tmp;}runtime:Trick to avoid repeatedly copying the value at A[1]Move down15Insert2014129118106754220141291181067542pqueue.insert(3)316Percolate Up201412911810675423 20141291183675421020141291185673421017Insert Codevoid 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:18Performance of Binary Heap•In practice: binary heaps much simpler to code, lower constant factor overheadBinary heapworst caseBinary heap avg caseAVL tree worst caseBST tree avg caseInsertO(log n) O(1)percolates 1.6 levelsO(log n) O(log n)Delete MinO(log n) O(log n) O(log n) O(log n)19Changing 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)20Other 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 …21BuildHeap•Task: Given a set of n keys, build a heap all at once•Approach 1: Repeatedly perform