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

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)

i am getting ur point??

what are you saying.

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.

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

but time complexity is remain same.

1
468 views
1 vote