Priority QueuesTwo kinds of priority queues:• Min priority queue.• Max priority queue.Min Priority Queue•Collection of elements.• Each element has a priority or key.• Supports following operations:isEmptysizeadd/put an element into the priority queueget element with min priorityremove element with min priorityMax Priority Queue•Collection of elements.• Each element has a priority or key.• Supports following operations:isEmptysizeadd/put an element into the priority queueget element with max priorityremove element with max priorityComplexity 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 queueApplicationsSorting• use element key as priority• put elements to be sorted into a priority queue• extract elements in priority orderif a min priority queue is used, elements are extracted in ascending order of priority (or key)if a max priority queue is used, elements are extracted in descending order of priority (or key)Sorting ExampleSort 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.After Putting Into Max Priority QueueSorted Array 68241Max Priority QueueAfter First Remove Max OperationSorted Array 62418Max Priority QueueAfter Second Remove Max OperationSorted Array 24186Max Priority QueueAfter Third Remove Max OperationSorted Array 21864Max Priority QueueAfter Fourth Remove Max OperationSorted Array 18642Max Priority QueueAfter Fifth Remove Max OperationSorted Array 86421Max Priority QueueComplexity Of SortingSort 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.Heap SortUses a max priority queue that is implemented as a heap.Initial put operations are replaced by a heap initialization step that takes O(n) time.Machine Schedulingm identical machines (drill press, cutter, sander, etc.)n jobs/tasks to be performedassign jobs to machines so that the time at which the last job completes is minimumMachine Scheduling Example3 machines and 7 jobsjob times are [6, 2, 3, 5, 10, 7, 14]possible scheduleABCtime ----------->6237131321Machine Scheduling ExampleFinish time = 21Objective:Find schedules with minimum finish time.ABCtime ----------->6237131321LPT SchedulesLongest Processing Time first.Jobs are scheduled in the order14, 10, 7, 6, 5, 3, 2Each job is scheduled on the machine on which it finishes earliest.LPT Schedule[14, 10, 7, 6, 5, 3, 2]ABC14107 13151616Finish time is 16!LPT Schedule•LPT rule does not guarantee minimum finish time schedules.• (LPT Finish Time)/(Minimum Finish Time) <= 4/3 - 1/(3m) where m is number of machines.• Usually LPT finish time is much closer to minimum finish time.• Minimum finish time scheduling is NP-hard.NP-hard Problems•Infamous class of problems for which no one has developed a polynomial time algorithm.• That is, no algorithm whose complexity is O(nk) for any constant k is known for any NP-hard problem.• The class includes thousands of real-world problems.• Highly unlikely that any NP-hard problem can be solved by a polynomial time algorithm.NP-hard Problems•Since even polynomial time algorithms with degree k > 3 (say) are not practical for large n, we must change our expectations of the algorithm that is used.• Usually develop fast heuristics for NP-hard problems.Algorithm that gives a solution close to best.Runs in acceptable amount of time.• LPT rule is good heuristic for minimum finish time scheduling.Complexity Of LPT Scheduling•Sort jobs into decreasing order of task time.O(n log n) time (n is number of jobs)• Schedule jobs in this order.assign job to machine that becomes available firstmust find minimum of m (m is number of machines) finish timestakes O(m) time using simple strategyso need O(mn) time to schedule all n jobs.Using A Min Priority Queue• Min priority queue has the finish times of the m machines.• Initial finish times are all 0.• To schedule a job remove machine with minimum finish time from the priority queue.• Update the finish time of the selected machine and put the machine back into the priority queue.Using A Min Priority Queue• m put operations to initialize priority queue• 1 remove min and 1 put to schedule each job• each put and remove min operation takes O(log m) time• time to schedule is O(n log m)• overall time isO(n log n + n log m) = O(n log (mn))Huffman CodesUseful in lossless compression.May be used in conjunction with LZW method.Read from text.Min Tree DefinitionEach tree node has a value.Value in any node is the minimum value in the subtree for which that node is the root.Equivalently, no descendent has a smaller value.Min Tree Example24 9 348 79 9Root has minimum element.Max Tree Example94 9 842 73 1Root has maximum element.Min Heap Definition• complete binary tree• min treeMin Heap With 9 NodesComplete binary tree with 9 nodes.Min Heap With 9 NodesComplete binary tree with 9 nodes that is also a min tree.246 7 9 38 63Max Heap With 9 NodesComplete binary tree with 9 nodes that is also a max tree.986 7 2 65 17Heap HeightSince a heap is a complete binary tree, the height of an n node heap islog2(n+1).9 8 7 6 7 2 6 5 11 2 3 4 5 6 7 8 9 100A Heap Is Efficiently Represented As An Array986 7 2 65 17Moving Up And Down A Heap986 7 2 65 1712 345 678 9Putting An Element Into A Max HeapComplete binary tree with 10 nodes.986 7 2 65 177Putting An Element Into A Max HeapNew element is 5.986 7 2 65 1775Putting An Element Into A Max HeapNew element is 20.98672 65 1777Putting An Element Into A Max HeapNew element is 20.98672 65 1777Putting An Element Into A Max HeapNew element is 20.98672 65 1777Putting An Element Into A Max HeapNew element is 20.98672 65 177720Putting An Element Into A Max HeapComplete binary tree with 11 nodes.98672 65 177720Putting An Element Into A Max HeapNew element is 15.98672 65 177720Putting An Element Into A Max HeapNew element is 15.98672 65 1777208Putting An Element Into A Max HeapNew element is 15.8672 65 1777208915Complexity Of PutComplexity is O(log n), where n is heap size.8672 65 1777208915Removing The Max ElementMax element is in the root.8672 65