The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
216 views
What is the time complexity of 'deleting any random node from a max or min heap'?
asked in DS by (125 points) | 216 views

1 Answer

+2 votes
Best answer
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 by
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

bad mistake

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,784 questions
54,511 answers
188,329 comments
75,114 users