Algorithm

Question

what is the time complexity of finding a number in a heap sort in worst case & what is the time complexity for deleting the element from heap?

Answer 1

In a heap, looking for an arbitrary element is O(n), thus removing an element [if given by value] is O(n) as well.

If your element is given by reference, it is however possible to remove it in O(logn) by simply 'replacing' it with the last leaf [remember a heap is implemented as a complete binary tree, so there is a last leaf, and you know exactly where it is], remove these element, and re-heapify the relevant sub heap.

Answer 2

I think you have some wording problems in this question.  
"Finding a number in heapsort" ???? Whats that?
or "Finding a number in a heap ?" or "Finding a number in a heap which is sorted" (I think you mean this one).

Searching: You are talking about any arbitrary element, It will take O(logn) to search. 
You can understand it in 2 ways.
Heap is stored in array, takes O(logn) to search in sorted array using binary search.
Or, understand it like... you may have to traverse till leaf in the tree. (Height of the tree is O(logn) you know. )

Deletion: To delete arbitrary element, you have to swap it with last element & call maxheapify/min heapify..which takes O(logn) but it does not ensure the heap will be sorted.. you need to follow the procedure of sorting from that node..as like u do heapsort.   O(n) is the answer.
You can understand it in other way like... In array .. remove & shift elements which will take O(n). 

I need to know where did I go wrong. Please give proper explanations. Thank you . :)

Comments

For searching an element to be deleted in heap sort it takes log(n) time nw replace it with last element of heap nw perform min   

heapify or max  heapify which can take atmost log(n) time so total time would be 2*log(n) plz correct if I am wrong

---

Maxheapify or Minheapify will help in fixing the heap property. It will not sort it.

---

For the purpose of searching an arbitrary element it won't take O(logn).. You have given the reason that if the elements were stored in array then it will be sorted and binary search can be applied.. But think once again does everytime the heap tree stored in array is always sorted.. No its not that is why it takes o(n) in searching..