IIIT PGEE 2019

Question

What is the time complexity to delete an arbitrary node from binary heap?

• A. O(n)
• B. O(log n)
• C. O(1)
• D. O(n log n)
   

Comments

But what about preserving the heap property again?? there would be some time required to make the heap property satisfiable again?

Answer 1

First let us know about what binary heap is: 

A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:

• the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
• the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.
• Also, a Binary Heap is a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.

 

The deletion of a random node would take O(n+log(n)) which equivalent to O(n) (worst case) as first we will find where the random element is in the heap which will take O(n) and then delete it which will further take O(log(n))

Therefore time complexity would be O(n)

Comments

As it is a complete tree but not balanced one that's why searching takes o(n) time if balanced one it would take o(logn) time

Answer 2

Logn it should be....if we are deleting a node in binary heap which is nothing but complete binary tree, we take last element put it at postion from where node is deleted then adjust it..

That is nothing but....O(1):for putting last element at position of deleted element.

O(Logn): for adjust .

1+Logn=logn

Comments

node to be deleted is to be searched in 0(n). Say if it is a MAX element in MIN heap. 0(n+logn)=0(n). cheers

Answer 3

Option A)O(n) , as the worst case complexity of deleting a node in binary heap is O(n)

Answer 4

The question has simply asked to delete an arbitrary node from binary heap.  It didn’t mention any best or worst case or for deleting all the nodes. Thus the average time is Θlogn. Option B is correct