edited by
31,688 views
79 votes
79 votes

In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time

  1. $\Theta (n \log n)$
  2. $\Theta (n)$
  3. $\Theta(\log n)$
  4. $\Theta(1)$
edited by

10 Answers

Best answer
142 votes
142 votes
Time to find the smallest element on a min-heap- one retrieve operation - $\Theta(1)$
Time to find the second smallest element on a min-heap- requires $2^2 - 1 = 3$ check operations to find the second smallest element out of $3$ elements - $\Theta(1)$

Time to find the $7^{th}$ smallest element - requires $O(2^7-1) = O(127)$ check operations to find the seventh smallest element out of $127$ possible ones - $\Theta(1)$

In short if the number of required operations is independent of the input size $n$, then it is always $\Theta(1)$.

(Here, we are doing a level order traversal of the heap and checking the elements)

If we are not allowed to traverse the heap and allowed only default heap-operations, we will be restricted with doing Extract-min $7$ times which would be $O(\log n)$.

Correct Answer: $D$
edited by
32 votes
32 votes
The 7th most element is always within the 7 levels from the root so we have constant number of nodes in worst condition .we need to check only constant number of nodes to find the 7th smallest number so constant time
5 votes
5 votes
The best known algorithm to find Kth smallest element in Min Heap takes - O(K*logK) time and here K = 7th element.

Thus we get O(7*log7) = O(1) as Answer.
1 votes
1 votes
3 approaches....
1st- Selection Sort
7 passes to find 7th minimum i.e. 7 × n = O(n)

2nd- Deletion from heap
Deletion of 1 element is logn
Deletion of 7 elements is 7 ×logn = O(logn)

3rd- sum of 1st 6 natural number in heap
O(1)

Among all 3 approaches 3rd one is best so option d is the answer.
Answer:

Related questions

25 votes
25 votes
3 answers
4
Kathleen asked Sep 16, 2014
23,358 views
Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering o...