Doubt on Heap

Question

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

Answer 1

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)

Comments

I am asking about only i-th element

---

by default min  heap delete root element. 

if you want 4th element. then it will delete like  

first element (root node), 2nd and 3rd like.

---

And what about a random element n ? If it has to be deleted then how much time it will take?

---

It will also take same time.....  Bcoz heap will delete always at root.

---

Okay. So in worst case, it has to delete all the nodes. Right? So in that case time comp should be n logn.

can it follow the following steps?

1. search the element. O(n) (in case of random element)

2. replace it with the last element

3. reduce the heapsize by 1.

4. apply Heapify on the replaced node.

---

replace mean delete node with last element???

but in heap we cant delete node from middle.

---

Sorry, instead of replacement I should have written exchange. In point 2

---

Why can't we delete a node from middle?

---

min heap is a almost complete binary tree .in this example after deleting node 4 . tree is not almost complete binary tree. so we cant do that

---

If we exchange 4 with 5 and delete 4,then? Doesn't it remain an almost complete binary tree? In case of BST it could not have been possible. But here why can't we do that

---

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.