CODEWITHSUNDEEP
algorithmheap
hytriutucx
hytriutucx

Reputation: 1634

Time complexity to get min elements from max-heap

I was asked in an interview:

What is the best time complexity in getting the min element(s) from a max-heap?

I replied as O(1) assuming the heap size is known and the heap is implemented as a binary heap using an array. This way as per my assumption, the min value is at heap_array[heap_size].

My question is that if this answer is correct. If not, what is the correct answer?

Upvotes: 14

Views: 43294

Answers (6)

ofir_aghai
ofir_aghai

Reputation: 3321

Best complexity is O(n).

Rather than, not wrote here a lot about that,
The min element in MAX-heap, and the MAX element in min-heap
Can be also at the (lowest level - 1) and not always in lowest level.

explain:
because in heap there is an option of missing nodes from the right side of the lowest level, it could be not a balancing (fully) tree, what makes it to have leafs also in (lower level -1).

what means that there are n/2 to check. so in big O term it's equal to O(n).

Examples for situation like that:

  • MAX-heap[10,9,1,8,7] (1 is the smaller value, but didnt apear in lowest level)
  • min-heap [8,10,20,17,15] (20 is the max value, but didnt apear in lowest level)

Upvotes: 0

Jugal Soni
Jugal Soni

Reputation: 1

Correct answer is O(n) 1) to find minimum element from max heap Find nth max(which is nothing but minimum element) Which will take n(n-1)/2 comparisons == O(n^2) 2) first at all it is array To find minimum element apply selection sort 1st pass Which will take O(n) time. 3) delete one by one (upto) n elements in max heap(it is nothing but finding only) Which will take O(nlogn) time. Among 3 ways the best one is O(n). So correct answer will be O(n) time

Upvotes: 0

Nitishgarg
Nitishgarg

Reputation: 119

MINIMUM_ELEMENT -> it will take O(n) time in case of Max heap and O(1) in case of Min heap. MAXIMUM_ELEMENT -> it will take O(1) time in case of Max heap and O(n) in case of Min heap.

Upvotes: 1

parimal
parimal

Reputation: 31

Min element from Max heap :

  1. search at last level = O(n/2)= O(n)

  2. replace searched element with last element and decrease heap size by 1 = O(1)

  3. Apply Maxheapify on replaced element = O(log n)

Total Time = O(n)+O(1)+O(log n) = O(n)

Upvotes: 1

Steve Jessop
Steve Jessop

Reputation: 279395

Best complexity is O(n). Sketch proof:

  • The minimum element could be absolutely any of the lowest-level nodes (in fact it could even not be at the lowest level, but let's start with these).
  • There could be up to n/2 lowest-level nodes.
  • All of them need to be examined, because the one you're looking for might be in the last place you look. Examining all-but-1 of them doesn't tell you whether the last one is the minimum or not.
  • Hence Omega(n) examinations required.

The bound is tight, since clearly we can do it in O(n) by ignoring the fact that our array happens to be a heap.

Moral: it's probably called a heap because (as with the heap of clothes on your bedroom floor) it's easy to get at the top and difficult to get at the rest.

Upvotes: 11

aioobe
aioobe

Reputation: 421290

My question is that if this answer is correct.

No, that's not correct. The only guarantee you have, is that each node contains the maximum element of the subtree below it. In other words, the minimum element can be any leaf in the tree.

If not what is the correct answer?

The correct answer is O(n). In each step you need traverse both left and right sub-trees in order to search for the minimum element. In effect, this means that you need to traverse all elements to find the minimum.

Upvotes: 35

Related Questions