#HeapSort

Question

What is the worst case time complexity of finding a element in max heap tree ?

Explain.

Comments

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.

Answer 1

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).

Comments

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,

---

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..

---

Ok Thank you I thought in wrong way sorry