Sir, can you explain me the time complexity of a min or a max heap. If insertion is done in O(n) then removing k elements should require O(k) as the elements are already sorted??
Time complexity of a heap
Hey
Removing k elements won’t take O(k) time! Elements aren’t sorted in a heap. Only the max/min element is available to us. So for every deletion, we delete the top element(O(n)), then heapify the heap (O(logn)).
So it take O(klogn) time.
But wait!
It is clear to us that every time we delete a node, n decreases. So complexity would be something less than O(nlogn).
Please give a read here for proof.
1 Like