Which of the following Binary Min Heap operation has the highest time complexity?
A) Inserting an item under the assumption that the heap has capacity to accommodate one more item
B) Deleting an item from heap
C) Merging with another heap under the assumption that the heap has capacity to accommodate items of other heap
D) Decreasing value of a key
Confused between option C and D. Please explain out of both which is correct and which one is not and why?
Correct Ans C (merging)
because merge operation takes O(n) time, all other operations given in question take O(Logn) time.
For Merging
We create an array to store result. We copy both given arrays one by one to result. Once we have copied all elements, we call standard build heap to construct full merged max heap.
Time Complexity : O(N)
For Decreasing Value of a Key
To decrease the value of a certain key, we’ll use the map to locate its index. because Searching is not simple in heaps
After we locate its index, we’ll change its value, and start moving it up the tree if needed.
Time Complexity : O(logN)
Space Complexity : O(N)
i hope now you understand the solution
happy coding
great explanation. thanks.
one thing i want to confirm is, if we do not use hashmap to search a key in heap, it would take O(n) time to search, right? Or is there any other way?
yes O(n) time
because then we have to linearly search on heap array