Applied Test Series

Question

The time required to determine the minimum element from the max heap of size O(log(n)) is given by

Comments

in max heap the smallest element always belong  at leaf node  and total leaf node on the last level is  approx n/2 compare it  is equal to O(n) in this question heap size logn so it is O(logn)

---

@LRU

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 …

 

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

In this question heap size logn , 

so it is O(logn)...

 

 

1. https://gateoverflow.in/889/Gate-cse-2006-question-10 

 

2. https://gateoverflow.in/295138/Finding-the-minimum-element-in-a-heap

 

 

Answer 1

Max element can be present in any of the leaf nodes of a min-heap.In a heap, the tree is a complete binary tree so the minimum element will be present either in the lowest level or second-lowest level, Now the number of elements we have to check(elements present in lowest and second-lowest level) is O(logn). So just by doing a linear search, you will get the element.

Answer : O(logn).

Ref: 

algorithm - Time complexity to get min elements from max-heap - Stack Overflow

https://gateoverflow.in/295138/Finding-the-minimum-element-in-a-heap

https://gateoverflow.in/889/Gate-cse-2006-question-10