TestBook Test Series Algo Q

Question

Q). What is the complexity of finding the $50^{th}$ smallest elements in an already constructed binary min-heap?

1. $\theta(1)$
2. $\theta(logn)$
3. $\theta(n)$
4. $\theta(nlogn)$

solution: 

Exact complexity would be $50logn$ for heapify when we do heap sort iteration $50$ times 

Answer 1

I think answer for this question should be O(1).

We need to find 50th smallest integer in min heap. Which can be easily done by checking first 2⁵⁰ no in arrays (Checking first 50 levels of heap !) .  It does not depend on size of heap. We can have min heap of size n =  2^2^50000000000still no of comparisons is fixed. It does not change with no of elements in heap.

Comments

How (k logk) ? I think this code takes k² ?

---

@Amsar: Here's a quick proof:

1. The while loop runs $k$ times, since in each iteration the number of nodes in the array smallestNodes increases by 1.
2. In each iteration, we remove 1 node from toVisit, and add at most 2 nodes to it. So, in each iteration, the number of nodes in toVisit can increase by at max 1.
3. toVisit is initially empty. Hence, after $k$ iterations, it can have at max $1 \times k = k$ nodes.
4. toVisit is a sorted list, which can be implemented as an independent min-heap. Insertion and deletion will be $O(\log k)$ operations (since maximum size of toVisit is $k$ as shown above). Hence, $k$ deletions and $2k$ insertions will take $O(k \log k)$ time.

PS: My bad, a sorted list cannot be realized as a min heap. However, all we need from toVisit is to always give us the minimum element on deletion and that is what the min heap does.

Also, we can implement a sorted list as a balanced-BST like AVL or Red-Black tree. So, it doesn't make a difference. The algorithm is $O(k \log k)$

---

thnks :)

I considered it a linear array..

Answer 2

finding smallest element from it is --

we have to apply extract minheap() whose time complexity is O(log n) 50 times i.e 50 log(n) and then O(1) for the 50th smallest number and then inserting the rest 49 element O(log n)*49.

total time complexity=50 log(n)+O(1)+49O(log n)=O(logn)