3 votes 3 votes Maximum element in a min-heap represented by an array, can be computed in _____ time $O(n)$ $O(\log n)$ $O(n \log n)$ but not $O(n)$ $O(1)$ Algorithms go-alogrithms-1 binary-heap algorithms + – Bikram asked Oct 4, 2016 • edited Oct 8, 2016 by Arjun Bikram 518 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 4 votes 4 votes Maximum element in a min-heap can be found only at the leaf. Total number of leaf nodes in a binary heap is exactly $\lceil \frac{n}{2}\rceil$ and there is no ordering among these elements and so we need $\lceil \frac{n}{2}\rceil$ comparisons to find the maximum. Being represented in an array, we can index to all leaf nodes in constant time. Hence, our required answer is $\Theta (n)$ which also implies $O(n).$ Correct option A. Ref: https://cs.stackexchange.com/questions/841/proving-a-binary-heap-has-lceil-n-2-rceil-leaves Digvijay Pandey answered Oct 11, 2016 • edited Dec 8, 2019 by Arjun Digvijay Pandey comment Share Follow See all 2 Comments See all 2 2 Comments reply Manoj_Kumar commented Jan 9, 2017 reply Follow Share "Since we cannot be sure of the minimum no. of elements in leaf we can only use O and not Θ" I am not getting this sentence can you please explian in detail. 0 votes 0 votes Decota commented Jan 16, 2017 reply Follow Share for finding Max element in min heap , we can heapify heap to max heap in Log(n) , and first element will be max element. So According to my concept it should be of O(log(n)) 0 votes 0 votes Please log in or register to add a comment.