2 votes 2 votes What is the worst case time complexity of finding a element in max heap tree ? Explain. Algorithms heap-sort + – S Harika asked Apr 1, 2017 edited Apr 1, 2017 by Prashant. S Harika 806 views answer comment Share Follow See 1 comment See all 1 1 comment reply rhl commented Jul 13, 2022 reply Follow Share In max-heap, all the minimum elements are at the last level. Therefore all of them are worst-case for finding any element in the heap. Let’s Suppose we are finding the minimum element in the max-heap. To go to the last level it will take us $O(log_2 n)$ amount of time. Searching minimum among the leaves will take us $O(\frac{n+1}{2}) = O(n)$. $O(log_2 n + n) = O(N)$ Here n is numbers of nodes in the tree. A complete binary tree with n nodes has at most $\frac{n+1}{2}$ nodes at the last level. 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes O(n). Its just a heap. Not sorted. Suppose you are searching a number very close to least element. You have to search in the leaves. Hence O(n). Ahwan answered Apr 1, 2017 selected Apr 1, 2017 by rude Ahwan comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Ahwan commented Apr 1, 2017 reply Follow Share If the heap is the output of heapsort then O(logn) ... But a heap is not sorted. It just follows that parent child property. If you will search least element in maxheap or max element in min heap, it will take O(n). Thats the worst case, 1 votes 1 votes Ahwan commented Apr 1, 2017 reply Follow Share Student2018, O(nlogn) Why ? Heap is stored in an array. Even a simple linear search will give in O(n). So O(nlogn) is not the answer.. 1 votes 1 votes student2018 commented Apr 1, 2017 reply Follow Share Ok Thank you I thought in wrong way sorry 0 votes 0 votes Please log in or register to add a comment.