Register

GATE CSE 2016 Set 1 | Question: 37

• edited by
15,261 views
56 votes
56 votes

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?

  1.  $O(1)$ 
  2.  $O(d)$ but not $O(1)$ 
  3.  $O(2^d)$ but not $O(d)$ 
  4.  $O(d \ 2^d)$ but not $O(2^d)$
• edited by
User Avatar

4 Answers

Best answer
61 votes
61 votes

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..

• edited by
User Avatar
11 votes
11 votes

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

User Avatar
2 votes
2 votes

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)$"​

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

73 votes
73 votes
5 answers
4
Akash Kanase asked Feb 12, 2016
25,870 views
GATE CSE 2016 Set 2 | Question: 34
A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth $0$. The maximum depth at which integer $9$ can appear is _________.
A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the h...
User Avatar
Link Copied!