In a binary max heap containing $n$ numbers, the smallest element can be found in time
^^ So you want to convert this Max Heap into a Min Heap and extract min ?
Okay, do so.
1) Make Min Heap from Max Heap: O(n) How ? Why O(n), shouldn't it be O(nlogn) ?
2) Extract Minimum: O(1)
3: Min Heapify: O(log n)
O(n) + O(1) + O(log n) = O(n)
@arjun sir .
In a max heap, the smallest element is always present at a leaf node. so for that we need to reach to leaf nodes that will take o(logn) time . after this bcz complete binary tree contain n/2 nodes on the leafs of tree .So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n/2)+logn so totaly worst case complexity is o(n) . am i right sir
Gatecse