recategorized by
630 views

2 Answers

Best answer
3 votes
3 votes

1). If we try to sort array by comparison based sorting ,,then it will take O(nlogn).

Then , finding minimum or maximum can be done in O(1).

2). Now, see procedure by a heap. Try to insert all these elements in max heap , it can be done

in O(nlogn), but if you efficiently use it, can be done in O(n) time . Now, we can get maximum in

O(1) time and if you want to extract it , then takes O(logn).

Hence, total complexity is O(n + logn) .

3). simple linear scan also will give O(n) .

So, finally best efficient complexity will be O(n) .

selected by
4 votes
4 votes

Creating heap itself take O(n) time . so cant be done in o(n). 

Procedure if u want to do by using heap.

creating heap = O(n) time  then O(1)  time to get the largest element. so total O(n).

Related questions

0 votes
0 votes
1 answer
1
Aboveallplayer asked Dec 1, 2016
662 views
You are given a heap containing N elements. Write a procedure which takes as input a parameter k, and outputs the k'th smallest number in the heap. The running time of th...
0 votes
0 votes
1 answer
2
Deepanshu asked Sep 12, 2018
624 views
If you are given a sorted list with n elements in ascending order. Then what will be the Time complexity to build a Min heap from the given array?
0 votes
0 votes
1 answer
3
Ayush Upadhyaya asked Jun 3, 2019
393 views
How in a heap there are at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of height h.
0 votes
0 votes
1 answer
4
eyeamgj asked Oct 16, 2018
322 views
what is correct definition m=of max heap?every node should be greater than its childrenorevery node should not be smaller than its children