Suppose you want to find the k-th smallest element from a collection of n given elements...

  

Transcribed Image Text:

Suppose you want to find the k-th smallest element from a collection of n given elements for a given k. (If k=1, then we want the smallest; if k=n; we want the largest, etc.). The elements are given in arbitrary order. Consider these two algorithms: // Algorithm 1 Build a min-heap on all n elements. Perform k delete-mins and return the result of the last delete min. // Algorithm 2 (idea: keep the k-smallest elements seen so far in 11 a heap; when done return max of them. Build a max-heap on the first k elements in the given sequence For each of the remaining n-k elements x{ if x is smaller than the largest element in the heap { do a delete-max insert x into the heap } //else heap unchanged return the max element in the heap after this process. Give a tight runtime analysis of each algorithm in terms of both n and k.. Algorithm 1: Algorithm 2: Suppose you want to find the k-th smallest element from a collection of n given elements for a given k. (If k=1, then we want the smallest; if k=n; we want the largest, etc.). The elements are given in arbitrary order. Consider these two algorithms: // Algorithm 1 Build a min-heap on all n elements. Perform k delete-mins and return the result of the last delete min. // Algorithm 2 (idea: keep the k-smallest elements seen so far in 11 a heap; when done return max of them. Build a max-heap on the first k elements in the given sequence For each of the remaining n-k elements x{ if x is smaller than the largest element in the heap { do a delete-max insert x into the heap } //else heap unchanged return the max element in the heap after this process. Give a tight runtime analysis of each algorithm in terms of both n and k.. Algorithm 1: Algorithm 2: