1,766 views
3 votes
3 votes

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

  1. O(n)
  2. O(log n)
  3. O(1)
  4. O(n log n)
     

4 Answers

5 votes
5 votes

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)

3 votes
3 votes
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
1 votes
1 votes
Option A)O(n) , as the worst case complexity of deleting a node in binary heap is O(n)
0 votes
0 votes

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

Related questions

3 votes
3 votes
4 answers
1
manikgupta123 asked Apr 28, 2019
1,658 views
What is the time complexity for insertion in binary tree in worst case?O(1)O(log n)O(n)O(n log n)
1 votes
1 votes
4 answers
2
manikgupta123 asked Apr 29, 2019
1,304 views
Which of the following gives O(1) complexity if we want to check whether an edge exists between two given nodes in a graph?Adjacency ListAdjacency MatrixIncidence MatrixN...
0 votes
0 votes
1 answer
3
manikgupta123 asked Apr 29, 2019
970 views
Which part in 8086 microprocessor is responsible for fetching instructions into the queue?BIUEUStackRegisters
3 votes
3 votes
2 answers
4
manikgupta123 asked Apr 28, 2019
1,085 views
How many pairs of positive integers do $m$ and $n$ satisfy in $\frac{1}{m}+\frac{4}{n}=\frac{1}{12}, $ where $n$ is odd and less than $60?$3579