Answers to below questions

#1

1.In what best time complexity you can merge two max-heaps?
(Assume size of first heap is (m+n) and the second is (n))

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

3.We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap.
The total time required for this is

4.Time taken in decreasing the node value in a binomial heap is

#2

Hi @Faizan-Ali-1395131367301898

  1. The complexity of merging the heaps is equal to O(n+n + m).
  2. The worst case complexity of deleting any arbitrary node value element from heap is O(logn) and for best case complexity is O(1)
  3. Inserting a new key takes O(Logn) time. So for inserting n keys it takes O(nlogn) time.
  4. Time complexity of decreaseKey() is O(Logn).
#3

Hi @Faizan-Ali-1395131367301898
Mark your doubt as resolved if you got all your answers.

#4

can you explain me 4th question answer

#5

Hi @Faizan-Ali-1395131367301898
In decreaseKey() we compare the decreases key with it parent and if parent’s key is more, we swap keys and recur for the parent. We stop when we either reach a node whose parent has a smaller key or we hit the root node so maximum times we need to perform this will be logn if there are n nodes that is why time complexity of decreaseKey() is O(Logn).

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.