3 votes 3 votes In a binary max heap containing $n$ numbers, the smallest element can be found in ______ $O(n)$ $O(\log _2 n)$ $O(1)$ $O(\log_2 \log_2 n)$ DS ugcnetcse-oct2020-paper2 data-structures binary-heap + – go_editor asked Nov 20, 2020 • recategorized Nov 27, 2020 by Krithiga2101 go_editor 1.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes In binary max heaps, smallest element will be present at leaves which resides from $\lceil\frac{n}{2}\rceil$ to $n$ location so we need to traverse at max $\frac{n}{2}$ elements which takes O(n)$ GATE 2006 Hence Option A) is correct Ashwani Kumar 2 answered Nov 23, 2020 Ashwani Kumar 2 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes https://www.geeksforgeeks.org/data-structures-and-algorithms-set-7/ Àbhíjèét Míshrà answered Dec 24, 2020 Àbhíjèét Míshrà comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n) cbkk answered Sep 16, 2023 cbkk comment Share Follow See all 0 reply Please log in or register to add a comment.