1 . For deleting any arbitrary element from a min heap in what best complexity you can achieve this?

#1

i think for deleting an element from a min heap the worst time complexity would be
logN
best time complexity is :—O( 1 ) if the element which we want to delete is present on the top of the min heap
i am correct or not??
the answer of this question is O(N) can you explain this ?

#2

best time complexity is not O(1) as if top element is to be deleted the first
we swap it with last node(or leaf node) then
delete last node then
call heapify function
so time complexity here is also log(n)

in Worst case
to delete an arbitrary node we may have to traverse the whole tree
because tree is not bst so node can be either side (left subtree or right subtree)
hence worst time complexity is O(n)

i hope this help
plz mark doubt as resolved from your side

1 Like