CSE310 Lecture 10: Priority Queues and Order StatisticsTopics of this lecturePriority QueuesSlide 4Slide 5Slide 6Slide 6Finding the smallest…Finding the smallestSmallest and 2nd smallest together…Finding 1st and 2nd smallest togetherFinding smallest and largest togetherFinding the largest and smallest togetherSlide 13Finding the kth smallestSlide 15Slide [email protected] Lecture 10:CSE310 Lecture 10:Priority Queues and Order StatisticsPriority Queues and Order StatisticsGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics 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 [email protected] QueuesPriority 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. itperforms 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 Swith the largest key.O(log n)[email protected] QueuesPriority 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 [email protected] QueuesPriority 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”elsemax = A[1]A[1] = A[heap-size[A]]heap-size[A]--HEAPIFY(A, 1)return [email protected] QueuesPriority QueuesINSERT(A, x)heap-size[A]++i = heap-size[A]while i > 1 and A[PARENT(i)] < x doA[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 [email protected]= 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]. . .  After applying HEAPSORT(A), A[n] > A[n-1] > … > A[1][email protected] the smallest…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 [email protected] the smallestFinding the smallestSmallest(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;[email protected] and 2Smallest and 2ndnd smallest together… 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 [email protected] 1Finding 1stst and 2 and 2ndnd smallest together 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 1st 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 1st and log(n) candidates for 2nd smallest in the group.logn-1 more [email protected] smallest and largest togetherFinding 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 [email protected] the largest and smallest togetherFinding the largest and smallest togethersmallestLargest(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;[email protected]= 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 An 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 [email protected] the kFinding the kthth smallest 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 [email protected]= 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 [email protected] medians of groupssort groups…group with fixed (constant) number of elements each.elements >