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

@Arjun Sir, I am having bit confusion in this question.

I am getting answer is C.

Here is my explanation

---

Since the heap tree is a having height d i.e. d edges from  root to farthest.

So there will be d+1 number of levels apparently level 0,level 1 .... level d+1.

Its heap so its a complete binary tree as well.

At level 0, we will be having 2⁰ = 1 node

At level 1, we will be having 2¹ = 2 nodes

At level 2, we will be having 2² = 4 nodes

.

.

.

.

At level d, we will be having 2^d nodes

-------------------------------------------------------

Total number of nodes = 1 + 2 + 4 + - - - - - - - - -  - + 2^d 

                                          =  1*(2^(d+1) - 1)/(2-1) = O(2^d)

So now in such a heap if you will delete the root node,then it will take O(2^d) to re-fix it efficiently.

So it think the answer should be (C) O(2^d) but not O(d)

Please tell me if any mistake i did.

Thanks.

---

for refixing the root.. it take O(h) time..

---

Sandeep if there are n elements in a heap then if you delete an element ,then in worst case it takes O(log n) time.Here place 2^d in place of n ,you will get the answer.

---

@Rajat Sharma 1

In general , deleting min element from min heap, takes O(log n) time because we call heapify function within the delete_min() itself.  But in the question it has asked to delete any random element with i^th index in array. So you don't know whether the remaining heap is fine or not.

So we will go with build heap method which will take O(n) and here n  = 2^d

---

@sandeep
Deleting any element in a heap always takes O(log n) for any element except in some cases where it can be O(1) also i.e.
1.When all element are same then deletion takes O(1).

2.When you delete leaf element.
Moreover Deleting ith index element can be handled by applying bottom heapify which takes O(log n) and it does not affect the element having less index than that element.

---

@Rajat Sharma 1

r u considering all the values of i.

because if so i may be root.

so you have n-1 to heapify.

---

@Sandeep.
If you need to delete root..
What we do..
we take the last element of array,copy to root, and reduce size of heap(array) by 1.
Then we compare the new root, with its children.. if any child is greater than the new root for a max heap, we swap the bigger of the the two children with the root.. then apply the same procedure at the swapped position,, in worst case this can propagate to the leaf of the tree.. which would take O(d) operations.
If you still have doubt, i would suggest,read Delete and Heapify algorithms from Cormen.. it would really clear all your doubts :)

---

But it takes O(1) when last node is deleted, so O(1) is also possible?

so why they have given "but not O(1)"?

---

No u have to consider worst case

i can be any node.

So, no need to consider it as last node.

O(1) case will be possible, if all possible cases accepts O(1),

---

If heap has n elements then in genral it takes O(n) to delete any $\; arbitary\;$ element. Because we first need to find that element, O(n) time and then delete that element O(height) [deleting involves swapping particular element to rightmost leaf and then do heapify on that node].
but good news here is, we don't need to find that element, because in delete(i), i is index of that element.
Delete time = O(height) = O(d)

---

I don't get the point of downvoting comments. If you think there is something wrong with a person's concepts or he/she is missing something, then clear it and explain if you know that, would be the better way. :)

---

Someone downvoted my above comment also :D

---

Why don't we need to rebuild the heap after removal of a random element?

---

When we replace an intermediate node with last node(say x), then we when x comes to new postion,it might go up or it might go down.So based upon this we decide one path in o(d) time.

---

arjun sir explained this concept very clearly already but link is not remember

---

(Considering a max heap):

Step1: Replace the key of the node to be deleted by infinity (or say largest value) using Increase key operation (takes O(d) time). Calling Increase key will float that node to the top(root) of the max-heap.

Step2: Replace the root node with the last element of the heap & decrease the size of the heap by 1 (takes O(1) time).

Step-3: Apply max heapify as the newly added element to the root may not satisfy the heap property. (takes O(d) time).

Hence the Total time would be of O(d). In case of min-heaps we would use minus infinity.

Source: Cormen

---

@Sachin Mittal 1 @Rajat Sharma 1 can you explain what will be the time complexity when all the elements of the heap are same.

---

@abhilashpanicker29 @Sachin Mittal 1

O(d) is same as saying O(log n) isn't it?

Where d is height and n is number of nodes

Please confirm if my understanding is correct!!

 

---

Why aren't we taking the case when last element can be deleting ! because in that case it will take O(1) time. So how can the answer be (B.) as it says Log(d) but not O(1)?

I know deleting an element take O(logn) if we know the index of the element!

---

@Shivam Kasat  after removal of element you have to maintain heap property ..that take d i.e logn.

" what is the time complexity to re-fix the heap efficiently after the removal of the element?"

 

---

@VIDYADHAR SHELKE 1 Yeah that's log(n) , To refix heap (so that heap satisfy heap property ) it takes Log(n) time.

---

Here they've defined "depth" same as the "height" of a node, but usually,

The depth of a node is the number of edges from that node to the tree's root node. ~Wikipedia

---

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