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

Question

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

//    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.

Discussion: why are these algorithms correct?

Algorithm 1:

Algorithm 2:

Discussion: why are these algorithms correct?

Explanation / Answer

Algorithm 1:

Algorithm 2

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.