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

after deleting the element which takes O(1) time complexity we swap the a[end] with the deleted element which again takes constant time.

now we need to heapify again either in max heap or min heap which takes logn or d .

---

the heapify operation is really really good as for any given a Heap... we can just plug any element with any other element inside the heap and now to fix everything... then we can just apply heapify at that particular node.
( works for both min/max heaps)

---

Deletion -> swap with last element -> heapify

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

@Deepak Poonia @Sachin Mittal 1 Is the word 'heapify' wrongly used by @abhilashpanicker29 in the answer? Because heapify means the process to first form a binary tree from a given array and then make it into a heap tree. THIS process takes O(n).

But here in this question we already have a heap and we are deleting an element, so only making changes to that one branch. Thus the time complexity must be O(height).

If anyone else can answer this doubt of mine, please do.

---

@TanayH

Heapify and BuildHeap are not same. You gave the definition of BuildHeap

---

A simple analogy is helpful to understand the relationship: Heapify is a single corrective action (the building block), whereas BuildHeap is the entire construction process.

• Heapify is a local subroutine that restores the heap property for a single sub-tree, assuming its children sub-trees are already valid heaps.
• BuildHeap is the overall algorithm that converts an entire unsorted array into a valid heap from scratch by repeatedly calling Heapify in a bottom-up order.

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

---

Deleting the root node will give us the most extreme case (since that would be the worst case in deletion), or the uppermost bound. Any node below the root will always take less comparisons than the ROOT case. So, by finding the big-O of root we are able to arrive at the upper bound,i.e, O(d).

 

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

Answer 5

When you remove an element like the root, you fill its spot with an element from the very bottom level (a leaf). This new element is likely out of place.

To restore the heap's order, this element must move down the tree, level by level, until it settles into its correct position. The longest journey this element can possibly take is from the root all the way back down to a leaf.

The length of this longest journey is exactly the depth (d) of the heap. Because the maximum number of steps is limited by the heap's depth, the time complexity is O(d), which is the same as O(logn).

Answer 6

IF WE DELETE AN ELEMENT FROM HEAP, THAN IN PLACE OF THAT DELETED ELEMENT, WE PUT THE LAST ELEMENT OF ARRAY (HEAP). AND THAN WE HEAPIFY THE HEAP. IT WILL COST LOGN COMPARISONS IE DEPTH OF HEAP. THEREFORE ANSWER WOULD BE LOGN IE DEPTH-d. not o(1).