retagged by
8,718 views
14 votes
14 votes

​​​​​Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$?

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

4 Answers

Best answer
20 votes
20 votes
In a min heap, maximum element is present in one of the leaf nodes.

If index of heap starts with $1,$ indices of leaves are $\lfloor n/2 \rfloor +1,\lfloor n/2 \rfloor +2,\lfloor n/2 \rfloor +3 \ldots n$.

So, we have to perform linear search on at most $n/2 +1$ elements to find the maximum element. (we cannot perform binary search since it is not guaranteed that leaves are in sorted order) and that multiplied by some constant $c$ will be the time complexity of the optimal algorithm. (Here, $c$ includes the cost of all operations which includes comparison, index shift etc. for a single maximum element compare)

In asymptotic terms, $c * (n/2 +1)$ is $\Theta(n).$
selected by
2 votes
2 votes
O(n)→ Searching in last level, can take theta(n) time as it might have max n/2 elements approx.
2 votes
2 votes
So by following the basics we know A min-heap contains smaller element as there parent. Now as soon as we go down our values start increasing. By observation, we can say that the last level must contain our maximum value. But we have to compare the last level of values. So how many elements we have to compare. SO as we know in heap n/2 elements are there which will be in leaves so we have to compare n/2 elements so COmplexity will be O(N)

Answer: C
0 votes
0 votes
N/2 nodes from beginning of array indexes are internal nodes. In Min Heap all the max nodes are available as leaves. So minimum can be found easily by running a loop over last N/2 elements.
Answer:

Related questions

14 votes
14 votes
4 answers
2
Arjun asked Feb 18, 2021
11,754 views
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$?$\Theta ( \sqrt{n})$$\Theta (\log _2(n))$$\Theta...
31 votes
31 votes
5 answers
3
Arjun asked Feb 18, 2021
7,667 views
Gauri said that she can play the keyboard __________ her sister.as well asas better asas nicest asas worse as