The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
227 views
I was going through the heap concept and one question came into my mind what will be the best case time complexity of finding the minimum element in a max heap?

Thank you:)
in DS by Active (1.3k points) | 227 views
0

@prashant jha 1

A quick look over the above algorithm suggests that the running time is O(nlg(n)), since each call to Heapify costs O(lg(n)) and Build-Heap makes O(n) such calls.
This upper bound, though correct, is not asymptotically tight.

 

0

You are correct there .

we are always provided with an unsorted array of elements and we build heap from it in O(n) time.

Only if we're provided with an array right? 

It's the best possible.

0

https://en.wikipedia.org/wiki/Binary_heap

Kindly have a read about building a heap.

I quote from it :-

Building a heap from an array of n input elements can be done by starting with an empty heap, then successively inserting each element. This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n log n) time: it performs n insertions at O(log n) cost each.[a]

However, Williams’ method is suboptimal. A faster method (due to Floyd[4]) starts by arbitrarily putting the elements on a binary tree, respecting the shape property

0

It's the best complexity possible . But this is only possible when we already have the elements present , can you say for sure than it will be O(n) if the heap is being from the scratch and elements are being added to the heap one after another?

its the worst complexity possible. O(n) denotes worst case complexity.

0
O(n) is worst? 😲 Then why people went for it?

Then what is O(nlogn) ?
0

@prashant jha 1

The case which you are mentioning will have a time space trade off because we are keeping input elements in one array and making heap in other array. so O(n) extra space would be required and that is also not the build heap algo.

that algo is william's method.

0
Bhai theek hai _/\_ :)
0
I think he meant best case complexity O(n)

edit: So, O(n) is the time taken for building a heap

that's the conclusion .
+1

conclusion : -

building heap by williams method takes O(nlogn) time. it does not uses max heapify technique.

building heap using max heapify takes O(n) time.

@prashant jha 1

@Nandkishor3939

thanks for the discussion.

1 Answer

+1 vote
Best answer
Minimum element in a Max heap will always be one of the leaf nodes of the heap.

Leaf nodes in heaps range from $\left \lfloor \frac{n}{2} \right \rfloor+1$  to $n$.

so in the worst case we need to check $\frac{n}{2}$ elements.

$\therefore$ time complexity is $\Omega (n)$ for finding minimum element in a max-heap in worst case.

OR

Assume that heap is stored in array and then we apply linear search on the second half of the array since all the leaf nodes will be in second half of the array

So T.C. = $\Omega (\frac{n}{2}) = \Omega(n)$
by Boss (19k points)
edited by
0
You should change best to worst case and big O to big Omega to make it precise.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,288 questions
55,719 answers
192,111 comments
90,122 users