CSE310 Lecture 10 Priority Queues and Order Statistics Guoliang Larry Xue Department of CSE Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture Priority Queues Order Statics Finding the smallest Finding both the smallest and the largest Finding the smallest and 2nd smallest Finding the kth smallest 2 Guoliang Xue asu edu Priority Queues A data structure for maintaining a set S of elements each with an associated value called a key A priority queue supports the following operations INSERT S x Inserts the element x into the set S i e it performs the operation S S x O log n MAXIMUM S returns the element in S with the largest key O 1 EXTRACT MAX S removes and returns the element in S with the largest key O log n 3 Guoliang Xue asu edu Priority Queues One application of priority queues is to schedule jobs on a shared computer the priority queue keeps track of the jobs to be performed and their relative priorities When a job is finished or interrupted the highest priority job that is still pending is selected using EXTRACT MAX We INSERT to add a new job to the queue at any time 4 Guoliang Xue asu edu Priority Queues The three operations on priority queues using a heap A the heap A represents the set S of elements MAXIMUM A return A 1 EXTRACT MAX A if heap size A 1 then error no elements to be extracted else max A 1 A 1 A heap size A heap size A HEAPIFY A 1 return max 5 Guoliang Xue asu edu Priority Queues INSERT A x heap size A i heap size A while i 1 and A PARENT i x do A i A PARENT i i PARENT i A i x How do we build a max heap How do we delete an arbitrary element How do we increase the key of an element How many heaps are there for the same set 6 Guoliang Xue asu edu HEAPSORT Any ideas What kind of properties does the heap have HEAPSORT A n BUILD HEAP A for i length A to 2 do n exchange A 1 and A i heap size A O n log n HEAPIFY A 1 O log n per call to HEAPIFY O n log n The maximum element of A is always stored at the root A 1 whenever this property is violated we immediately fix it with HEAPIFY Thus it can be correctly put in place by exchanging A 1 with A heap size A Let n length A A n contains maximum element in A 1 n A n 1 contains second maximum element in A 1 n Guoliang Xue asu edu 7 A n A n 1 A 1 After applying HEAPSORT A Finding the smallest How can we find the smallest of n elements Make n 1 comparisons Can we do with fewer comparisons No we need n 1 comparisons to identify the smallest element 8 Guoliang Xue asu edu Finding the smallest Smallest A n xv A 1 xi 1 for i 2 i n i if A i xv then xv A i xi i return xi 9 Guoliang Xue asu edu Smallest and 2nd smallest together Using the previous algorithm we can find the smallest and 2nd smallest with n 1 n 2 comparisons We can also find both the smallest and the second smallest elements using n log n 2 comparisons How n 1 comparisons to find the smallest element The second smallest element is in a group of log n elements 10 Guoliang Xue asu edu Finding 1st and 2nd smallest together In n 2 comparisons we have n 2 groups of 1st and 1 candidate for 2nd smallest in each group In n 4 comparisons we have n 4 groups of 1 st and 2 candidates for 2nd smallest in each group In n 2k comparisons we have n 2k groups of 1st and k candidates for 2nd smallest in each group In 1 comparison we have 1 group of 1 st and log n candidates for 2nd smallest in the group logn 1 more comparisons 11 Guoliang Xue asu edu Finding smallest and largest together We can find the smallest in n 1 comparisons and then find the largest in n 2 comparisons This requires a total of 2n 3 comparisons We can do this in 3n 2 1 comparisons 12 Guoliang Xue asu edu Finding the largest and smallest together smallestLargest A n if A 1 A 2 then x A 1 y A 2 else x A 2 y A 1 for i 3 i n i i 2 compare A i and A i 1 let xx be the smaller and yy be the larger if xx x then x xx if yy y then y yy print x y 13 Guoliang Xue asu edu Selection Problems Problem Given a set A of n elements and an integer k we want to find the kth smallest element in A If k 1 we want to find the minimum element of A If n is odd and k n 1 2 we are looking for the median of A n is even and k n 2 the two medians of S are the kth and k 1 th elements of S If k n we want to find the maximum element of A How can we solve this problem in O n log n time Sort S then simply index kth element of S Can we do any better How about the case when we are searching for the minimum maximum element 14 Guoliang Xue asu edu Finding the kth smallest Choose a pivot element x Partition the array using x as the pivot Let x be the jth element If j k DONE If j k find the kth element in the left portion If j k find the k j th element in the right portion How good is this 15 Guoliang Xue asu edu Worst Case Linear Time Selection That is the algorithm that we present for the k selection problem runs in time O n This algorithm is not very intuitive Idea recursively partition the array into subarrays then solve problems recursively find a good split of the array the algorithm uses a modified version of the quicksort PARTITION procedure where we take the pivot element around which we do the partition as a parameter 16 Guoliang Xue asu edu sort medians of groups sort groups group with fixed constant number of elements each 17 x elements x Guoliang Xue asu edu Summary Finding smallest and largest together Finding smallest and 2nd smallest togetgher Finding the kth smallest 18 Guoliang Xue asu edu Readings The materials covered in this lecture can be found in Section 9 1 19 Guoliang Xue asu edu
View Full Document
Unlocking...