in DS retagged by
736 views
0 votes
0 votes
How much time will it take for deleting $i^{th}$ and a number $n(random)$ node from a heap?
in DS retagged by
736 views

1 Answer

0 votes
0 votes

if you have a heap(either min or max) if we delete first element then it coll heapify . and it will take logn .

so delete 1st element ------------->logn

delete 2nd element------------->logn

           ;

            ;

delete ith element --------------> logn 


logn +logn+logn.................(upto i)

logn(1+1+............................)

logn * i

i(logn)------> O(logn)

4 Comments

i am getting ur point??

what are you saying.
0
0

we have to delete node 4 in the pic posted by you. right?

you are saying "if we delete node 4 our heap doesn't remain an almost complete binary tree. So it is violating heap property."

I am saying that we don't need to delete the node 4 directly. We can follow the following steps and actually can delete a node from heap even that is in middle:

1. Exchange the node to be deleted with the last node of the heap. here node 4 will be exchanged with node5.

2. reduce heap size by 1. thus node 4 is being deleted 

3 Now apply max or min heapify on node 5.

Why can't we do this and delete the required node?

 Here heap property is also being preserved.

0
0
yes we can do this.and i think it is right.

but time complexity is remain same.
0
0