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 | 227 views
0

@prashant jha 1

A quick look over the above algorithm suggests that the running time is , since each call to Heapify costs and Build-Heap makes 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

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 vote
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.

1
2
+1 vote