资源描述
Outline of LectureqADT Priority QueueLinear List RepresentationqHeap Data Structure(better alternative to implementing priority queue)qSections 9.1,9.2,and 9.32004-31L.ChenPriority QueuenMany situations where we need to choose the next element based on its importance or“priority”rather then based on arrival order,for examplenScheduling in multi-tasking environmentnHandling patients in emergency roomnCollection of objects organized by importance is called priority queuenMin and max priority queues depending on the order in which elements are inserted/returned 2004-32L.ChenADT Priority Queue(Min,Max)Mathematical modelnFinite collection of elements,each has a priorityOperationsnisEmpty():returns true iff the queue is emptynsize():returns number of elements in queuengetMax(),getMin():return element with maximum(minimum)prioritynput(x):inserts element x into queuenremoveMax(x),removeMin():remove element with largest(smallest)priority from the queue and return element2004-33L.ChenA Word About ImplementationnA normal queue not well suited for implementing priority queuenmust search for element with highest/lowest priority if list is unsorted:(n)nalternatively:maintain sorted list is(n)nNee to find a data structure that is guaranteed to have good performance for this special application2004-34L.ChenThe Heap Data StructureA heap is defined by two properties:1)It is a complete binary tree,so heaps can be efficiently implemented using an array representation 2)The values stored in a heap are partially ordered.This means that there is a relationship between the value stored at any node and the values of its childrennTwo variants of the heap data structure,depending on definition of this partial ordering2004-35L.ChenMin/Max-HeapsDefinition Max-Heap:nEvery node stores a value that is greater than or equal to the value of its childrennRoot stores maximum of all values in treeDefinition Min-Heap:nEvery node stores a value that is less then or equal to that of its childrennRoot stores minimum of all values in tree2004-36L.ChenMin Priority QueuenCollection of elements.nEach element has a priority or key.nSupports following operations:isEmptysizeadd/put an element into the priority queueget element with min priorityremove element with min priority2004-37L.ChenMax Priority QueuenCollection of elements.nEach element has a priority or key.nSupports following operations:isEmptysizeadd/put an element into the priority queueget element with max priorityremove element with max priority 2004-38L.ChenComplexity Of OperationsTwo good implementations are heaps and leftist trees.isEmpty,size,and get=O(1)timeput and remove=O(log n)time where n is the size of the priority queue2004-39L.ChenExamples991895158030105454030max heapmax heapmin heap89951810min heap2004-310L.ChenNotesnNot necessarily a relationship between a node and its siblingnBoth heaps have different usesnHeap Sort(max heap)nReplacement selection algorithm(min heap)nDo not confuse logical representation of heap(tree structure)with its physical implementation(one dimensional array)nHeap with n elements,height h=log2(n+1)n if cost of operations put and remove proportional to h,then running time O(logn)2004-311L.ChenOperations on Heap2004-312L.ChenInsertion into Max Heap201521410201521411012115201421020155141052212004-313L.ChenSummary and AnalysisnDetermine the structure of the new heap firstnMust satisfy complete binary tree principlenMove up the tree,swapping nodes as necessarynSingle pass from newly inserted leaf towards root Analysis:nAt each level,spent constant amount of time:(1)nNumber of levels is h running time bounded by O(h)or O(logn)2004-314L.ChenDeletion from Max Heap1520141022120152141015214102015142102004-315L.ChenSummary and AnalysisnRemove root element onlynMust maintain complete binary tree structurenSingle pass from root towards a leaf,filling the hole with the larger of the two childrennFollowing the gap down the tree until we reach leaf Analysis:nAt each level,spent constant amount of time:(1)nNumber of levels is h running time bounded by O(h)or O(logn)2004-316L.ChenInitialization of Max HeapnAssume n elements;two options(1)n calls to insert,resulting in O(nlogn)running time(2)special initialization strategy,(n)running timenAssume all n elements are available at the beginning of initialization processnSequence of exchanges of elements to build up heap2004-317L.ChenInitial ScenarionArray a of n elements a1.10nPriorities are 20,12,35,15,10,80,30,17,2,1201235158030101712123456789102004-318L.ChenRecall:Formula-Based RepresentationnUse array to store elementsnElement numbers are used as array indicesnAssume complete binary tree(with missing elements)nLeave empty cells in the arraynUse properties of complete b.t.to calculate array indices(see previous slide)ABC1234567ABC012345672004-319L.ChenRearrangementnStart with first node that has child;node at position a5 with priority 10nlocated at i=n/2nIf not max heap,adjustnContinue with subtrees rooted at i-1,i-2,1,examining the entire binary tree2004-320L.ChenFirst Step:i=520123515803010171212345678910Ok!2004-321L.ChenSecond Step:i=420123515803010171212345678910Not max heap!2004-322L.ChenExchange 15 with 1720123517803010151212345678910ok!2004-323L.ChenThird Step:i=320123517803010151212345678910Exchange 80 and 352004-324L.ChenFourth Step:i=220128017353010151212345678910Exchange 17 and 12,and 12 and 152004-325L.ChenFinal Step:i=1(root)20178015353010121212345678910Exchange 80 and 20,and 20 and 352004-326L.ChenFinal Max Heap801735152030101212123456789102004-327L.ChenApplications Heap Sort Machine Scheduling Huffman Codes2004-328L.ChenSorting1.use element key as priority2.put elements to be sorted into a priority queue3.extract elements in priority order1.if a min priority queue is used,elements are extracted in ascending order of priority(or key)2.if a max priority queue is used,elements are extracted in descending order of priority(or key)2004-329L.ChenSorting ExamplenSort five elements whose keys are 6,8,2,4,1 using a max priority queue.Put the five elements into a max priority queue.Do five remove max operations placing removed elements into the sorted array from right to left.2004-330L.ChenAfter Putting Into Max Priority QueueSorted Array 68241Max Priority Queue2004-331L.ChenAfter First Remove Max OperationSorted Array 62418Max Priority Queue2004-332L.ChenAfter Second Remove Max OperationSorted Array 24186Max Priority Queue2004-333L.ChenAfter Third Remove Max OperationSorted Array 21864Max Priority Queue2004-334L.ChenAfter Fourth Remove Max OperationSorted Array 18642Max Priority Queue2004-335L.ChenAfter Fifth Remove Max OperationSorted Array 86421Max Priority Queue2004-336L.ChenComplexity Of SortingnSort n elements.n put operations=O(n log n)time.n remove max operations=O(n log n)time.total time is O(n log n).compare with O(n2)for sort methods of Chapter 2.2004-337L.ChenHeap SortnUses a max priority queue that is implemented as a heap.nInitial put operations are replaced by a heap initialization step that takes O(n)time.2004-338L.ChenMachine Schedulingm identical machines(drill press,cutter,sander,etc.)n jobs/tasks to be performedassign jobs to machines so that the time at which the last job completes is minimum2004-339L.ChenMachine Scheduling Example3 machines and 7 jobsjob times are 6,2,3,5,10,7,14possible scheduleABCtime-62371313212004-340L.ChenMachine Scheduling ExampleFinish time=21Objective:Find schedules with minimum finish time.ABCtime-62371313212004-341L.ChenLPT SchedulesnLongest Processing Time first.nJobs are scheduled in the ordern14,10,7,6,5,3,2nEach job is scheduled on the machine on which it finishes earliest.2004-342L.ChenLPT Schedule14,10,7,6,5,3,2ABC1410713151616Finish time is 16!2004-343L.ChenLPT SchedulenLPT rule does not guarantee minimum finish time schedules.n(LPT Finish Time)/(Minimum Finish Time)3(say)are not practical for large n,we must change our expectations of the algorithm that is used.n Usually develop fast heuristics for NP-hard problems.Algorithm that gives a solution close to best.Runs in acceptable amount of time.nLPT rule is good heuristic for minimum finish time scheduling.2004-346L.ChenComplexity Of LPT SchedulingnSort jobs into decreasing order of task time.O(n log n)time(n is number of jobs)nSchedule jobs in this order.1.assign job to machine that becomes available first2.must find minimum of m(m is number of machines)finish times3.takes O(m)time using simple strategy4.so need O(mn)time to schedule all n jobs.2004-347L.ChenUsing A Min Priority QueuenMin priority queue has the finish times of the m machines.nInitial finish times are all 0.nTo schedule a job remove machine with minimum finish time from the priority queue.nUpdate the finish time of the selected machine and put the machine back into the priority queue.2004-348L.ChenUsing A Min Priority Queuenm put operations to initialize priority queuen1 remove min and 1 put to schedule each jobneach put and remove min operation takes O(log m)timentime to schedule is O(n log m)noverall time is O(n log n+n log m)=O(n log(mn)2004-349L.ChenHuffman CodesnUseful in lossless compression.nMay be used in conjunction with LZW method.nRead from text.2004-350L.ChenMin Tree DefinitionnEach tree node has a value.nValue in any node is the minimum value in the subtree for which that node is the root.nEquivalently,no descendent has a smaller value.2004-351L.ChenMin Tree Example249348799Root has minimum element.2004-352L.ChenMax Tree Example949842731Root has maximum element.2004-353L.ChenMin Heap Definitionncomplete binary treenmin tree2004-354L.ChenMin Heap With 9 NodesComplete binary tree with 9 nodes.2004-355L.ChenMin Heap With 9 NodesComplete binary tree with 9 nodes that is also a min tree.2467938632004-356L.ChenMax Heap With 9 NodesComplete binary tree with 9 nodes that is also a max tree.9867265172004-357L.Chen Heap HeightSince a heap is a complete binary tree,the height of an n node heap is log2(n+1).2004-358L.Chen987672651123456789100A Heap Is Efficiently Represented As An Array9867265172004-359L.ChenMoving Up And Down A Heap9867265171234567892004-360L.ChenPutting An Element Into A Max HeapComplete binary tree with 10 nodes.98672651772004-361L.ChenPutting An Element Into A Max HeapNew element is 5.9867265177 52004-362L.ChenPutting An Element Into A Max HeapNew element is 20.986726517772004-363L.ChenPutting An Element Into A Max HeapNew element is 20.986726517772004-364L.ChenPutting An Element Into A Max HeapNew element is 20.986726517772004-365L.ChenPutting An Element Into A Max HeapNew element is 20.98672651777202004-366L.ChenPutting An Element Into A Max HeapComplete binary tree with 11 nodes.9867265177720 2004-367L.ChenPutting An Element Into A Max HeapNew element is 15.9867265177720 2004-368L.ChenPutting An Element Into A Max HeapNew element is 15.986726517772082004-369L.ChenPutting An Element Into A Max HeapNew element is 15.86726517772089152004-370L.ChenComplexity Of PutComplexity is O(log n),where n is heap size.86726517772089152004-371L.ChenRemoving The Max ElementMax element is in the root.86726517772089152004-372L.ChenRemoving The Max ElementAfter max element is removed.867265177789152004-373L.ChenRemoving The Max ElementHeap with 10 nodes.86726517778915Reinsert 8 into the heap.2004-374L.ChenRemoving The Max ElementReinsert 8 into the heap.6726517779152004-375L.ChenRemoving The Max ElementReinsert 8 into the heap.6726517779152004-376L.ChenRemoving The Max ElementReinsert 8 into the heap.67265177791582004-377L.ChenRemoving The Max ElementMax element is 15.67265177791582004-378L.ChenRemoving The Max ElementAfter max element is removed.672651777982004-379L.ChenRemoving The Max ElementHeap with 9 nodes.672651777982004-380L.ChenRemoving The Max ElementReinsert 7.626517982004-381L.ChenRemoving The Max ElementReinsert 7.626517982004-382L.ChenRemoving The Max ElementReinsert 7.6265179872004-383L.ChenComplexity Of Remove Max ElementComplexity is O(log n).6265179872004-384L.ChenInitializing A Max Heapinput array=-,1,2,3,4,5,6,7,8,9,10,1184767893710111522004-385L.ChenInitializing A Max HeapStart at rightmost array position that has a child.8476789371011152Index is n/2.2004-386L.ChenInitializing A Max HeapMove to next lower array position.84767893710151122004-387L.ChenInitializing A Max Heap84767893710151122004-388L.ChenInitializing A Max Heap89767843710151122004-389L.ChenInitializing A Max Heap89767843710151122004-390L.ChenInitializing A Max Heap89763847710151122004-391L.ChenInitializing A Max Heap89763847710151122004-392L.ChenInitializing A Max Heap897638477101511Find a home for 2.2004-393L.ChenInitializing A Max Heap8976384775111Find a home for 2.102004-394L.ChenInitializing A Max Heap8976384772111Done,move to next lower array position.1052004-395L.ChenInitializing A Max Heap8976384772111105Find home for 1.2004-396L.Chen11Initializing A Max Heap8976384772105Find home for 1.2004-397L.ChenInitializing A Max Heap897638477211105Find home for 1.2004-398L.ChenInitializing A Max Heap897638477211105Find home for 1.2004-399L.ChenInitializing A Max Heap897638477211105Done.12004-3100L.ChenTime Complexity8763477101152981Height of heap=h.Number of subtrees with root at level j is=2 j-1.Time for each subtree is O(h-j+1).2004-3101L.ChenComplexityTime for level j subtrees is=s(rightChild(x)2004-3111L.ChenA Leftist Tree00000000001112112122004-3112L.ChenLeftist Trees-Property 1nIn a leftist tree,the rightmost path is a shortest root to external node path and the length of this path is s(root).2004-3113L.ChenA Leftist Tree0000000000111211212Length of rightmost path is 2.2004-3114L.ChenLeftist TreesProperty 2nThe number of internal nodes is at leastn2s(root)-1nBecause levels 1 through s(root)have no external nodes.nSo,s(root)=log(n+1)2004-3115L.ChenA Leftist Tree0000000000111211212Levels 1 and 2 have no external nodes.2004-3116L.ChenLeftist TreesProperty 3nLength of rightmost path is O(log n),where n is the number of nodes in a leftist tree.nFollows from Properties 1 and 2.2004-3117L.ChenLeftist Trees As Priority QueuesMin leftist tree leftist tree that is a min tree.Used as a min priority queue.Max leftist tree leftist tree that is a max tree.Used as a max priority queue.2004-3118L.ChenA Min Leftist Tree8696854322004-3119L.ChenSome Min Leftist Tree Operationsput()remove()meld()initialize()put()and remove()use meld().2004-3120L.ChenPut Operationput(7)8696854322004-3121L.ChenPut Operationput(7)869685432Create a single node min leftist tree.72004-3122L.ChenPut Operationput(7)869685432Create a single node min leftist tree.Meld the two min leftist trees.72004-3123L.ChenRemove Min8696854322004-3124L.ChenRemove Min869685432Remove the root.2004-3125L.ChenRemove Min869685432Remove the root.Meld the two subtrees.2004-3126L.ChenMeld Two Min Leftist Trees869685436Traverse only the rightmost paths so as to get logarithmic performance.2004-3127L.ChenMeld Two Min Leftist Trees869685436Meld right subtree of tree with smaller root and all of other tree.2004-3128L.ChenMeld Two Min Leftist Trees869685436Meld right subtree of tree with smaller root and all of other tree.2004-3129L.ChenMeld Two Min Leftist Trees866846Meld right subtree of tree with smaller root and all of other tree.2004-3130L.ChenMeld Two Min Leftist Trees86Meld right subtree of tree with smaller root and all of other tree.Right subtree of 6 is empty.So,result of melding right subtree of tree with smaller root and other tree is the other tree.2004-3131L.ChenMeld Two Min Leftist TreesSwap left and right subtree if s(left)s(right).Make melded subtree right subtree of smaller root.8668682004-3132L.ChenMeld Two Min Leftist Trees866648866468Make melded subtree right subtree of smaller root.Swap left and right subtree if s(left)s(right).2004-3133L.ChenMeld Two Min Leftist Trees953Swap left and right subtree if s(left)s(right).Make melded subtree right subtree of smaller root.8666482004-3134L.ChenMeld Two Min Leftist Trees9538666482004-3135L.ChenInitializing In O(n)Timencreate n single node min leftist trees and place them in a FIFO queuenrepeatedly remove two min leftist trees from the FIFO queue,meld them,and put the resulting min leftist tree into the FIFO queuenthe process terminates when only 1 min leftist tree remains in the FIFO queuenanalysis is the same as for heap initialization2004-3136L.Chen
展开阅读全文