time complexity

Question

time taken to delete a node from min heap if you know the value but not position

To find the position of the number  in min heap should not be log(n)

why is it so O(n)

Comments

Because there is no relative order between siblings so nothing like binary search can be applied like in BST,

---

in min heap specific number can be found in O(n) only because unlike BST you dont know whether to go right subtree or left subtree....therefore in worst case you need to traverse entire tree(min heap) in O(n)

---

your algorithm demands Element to be searched in the heap and then deleted.

• $O( n)\,\, \text{for searching element }$
• $O(\log\, n)\,\, \text{for delete that element (actually deleting will take constant time , but then maintaining heap property will take logn time so eventually O(logn)) }$

$O(n)+O(\log\, n)$, hence $O(n)$

Answer 1

Since we don't know the position of the element to be deleted, we need to search that element and then delete it.

For searching in a heap (be it min or max), we need to go through all the elements of the heap. Because there is no total ordering of the heap elements. There is no relation between the siblings of a node. So, searching will take O(n).

Now for deletion, it will take O(logn).

This gives total complexity = O(n) + O(logn) = O(n)

Comments

Correct above:

Now for deletion, it will take O(logn).

This gives total complexity = O(n) + O(logn) = O(n)

Total complexity = O(n) + O(n logn) = O(n logn)

---

Thanks @Shivam. Corrected.