+1 vote
216 views
What is the time complexity of 'deleting any random node from a max or min heap'?
asked in DS | 216 views

The deletion of a random node would take $O(n+log(n))$ as first we will find where the random element is in the heap which will take $O(n)$ and then delete it which will further take $O(log(n))$
answered by Active (5.1k points)
selected
0
Thanks
+1
Find the node which has to be delete, decrease the key to -INF (in case of min heap), now your element is at root position, Now apply Extract MIN operation.

∴ O(n) + O(log n) + O(log n) = O(n)
0
I think it's O( log n)

To finding a element in a min heap : O ( logn)

Then apply deletion takes : O ( log n)
0

@Magma

how can you find an element with in O(log n) time in HEAP ?

0
True, searching takes O ( n) time in heap .
0
O sorry

1
2