GATE CSE 2016 Set 1 | Question: 37

Question

An operator $delete(i)$ for a binary heap data structure is to be designed to delete the item in the $i$-th  node. Assume that the heap is implemented in an array and $i$ refers to the $i$-th index of the array. If the heap tree has depth $d$ (number of edges on the path from the root to the farthest leaf ), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

• A.  $O(1)$ 
• B.  $O(d)$ but not $O(1)$ 
• C.  $O(2^d)$ but not $O(d)$ 
• D.  $O(d \ 2^d)$ but not $O(2^d)$

Comments

delete operator delete(i) given ->  delete the ith node hence -> takes O(1) time but we need to maintain heap property hence 

we replace last node to removal node (easily get last node in O(1) in array heap representation ) and this takes again O(1) time since we already know ith index. But after replacement to the last node we need to apply Heapify that usually takes O(logn) but it is already given that 

If the heap tree has depth d (number of edges on the path from the root to the farthest leaf ),

hence Heapify max can take O(d) that should be the answer.

I hope it helps !

 

---

Heapify takes $O(logn)$ time. Height and depth of a heap are also $O(logn)$

So, we can equivalently say Heapify takes $O(logn) \ or \ O(d) \ or \ O(h)$ time.

---

Alternatively, since we know that heapify takes $O(logn)$ time, where n is the number of elements...

If a heap has depth d, it can have $O(2^d)$ elements

So, heapify takes $O(log2^d)=O(d)$ time

---

Please refer to this article for a clear understanding of the concept. http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-delete.html

Answer 1

Answer would be (B) $O(d)$ but not $O(1)$.. as we need to apply heapify.. and suppose if we are deleting root, in worst case would take $O(d)$ time..

Comments

Can anyone explain why can't we use Build Max Heap instead of Max Heapify at root after moving the ith element to last element and reducing heap size by 1?

---

@Shivateja

We can’t use because in buildMaxHeap already maxheapify is there..

and it will increase the time complexity to O(n).

and maxheapify take only O(logn) and also this is not practical because in buildMaxHeap we go from floor(n/2) down to 1 and each time we appying buildMaxHeapify procedure there and you are saying for the root only so no need of traversing this much.

REF :  https://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf

---

If anyone has any confusion in "not O(1) " part of option B :

If I say that a problem can be solved in O(1) time then it means that on ALL instances of that problem, I will need only constant time.

So that's why for this question answer can not be O(1) ..
So O(n) is answer But not O(1)..

If this problem can be solved in O(1) time then comparison-based sorting can be done in O(n) time (using heap sort) which contradicts the fact that any comparison based sorting should take at least nlogn time in worst case.

Answer 2

here d= 2  now in worst case rooti.e. 50 will be deleted. so max 2(and 2 comparoision needed) swap needed . so for d length O(d) time will be needed .

since O(1) is also given b/c if we delete leaf node i.e. 33 then noneed to do anything.

So B is answer

Comments

it can be a random node too. Not only root we have to consider

Answer 3

The question is about the time complexity of deleting an item in a binary heap.

A binary heap is a complete binary tree, which can be efficiently implemented as an array. The operations on a binary heap, like insert, delete, and extract max (or min for a min heap), involve maintaining the heap property after the operation. This is usually done using a procedure called "heapify" or "sift-down" that moves a node down the tree, swapping it with its children until the heap property is restored.

The operation delete(i) is supposed to delete the i-th node in the heap. Deleting a node involves two steps:

1. Replace the node to be deleted with the last node in the heap.
2. Heapify the heap to restore the heap property.

The replacement operation takes constant time, O(1), because we're dealing with an array and we have direct access to any element.

Heapify is the operation that can take more time. In the worst case, a node might have to be moved down the tree all the way to the leaf level. Since the heap is a complete binary tree, its depth d is approximately equal to log(n) where n is the number of nodes in the heap.

Therefore, the worst-case time complexity of the delete(i) operation is dominated by the heapify step, which is O(d), where d is the depth of the heap.

So, the answer to the question is "2. $O(d)$ but not $O(1)$"​

Comments

well explained

Answer 4

Answer is B.

Read cormen 142 page,Exercise 6.5-7...

http://stackoverflow.com/questions/15429164/deleting-in-a-heap-why-does-this-implementation-switch-the-values-of-the-last-e

Comments

In 3^rd edition : page 166 Q 6.6-8