I have a minimum heap with n elements and want to find k smallest numbers from this heap. What is the worst-case complexity?
Here is my approach: somewhere on the stackoverflow I read that complexity of finding i-th smallest number in a min heap is O(i). So if we would like to find n-1 smallest numbers (n is pointless, since it would be the entire heap), the total complexity would look something like this:
O(n-1)+O(n-2)+O(n-3)+…+O(2)+O(1)=O((1+n-1)*(n/2))=O(n^2)
Is this correct?
No, the time is much better than that. O(k log(n)) very easily, and O(k) if you're smart.
Finding and removing the smallest element from the heap is O(log(n)). This leads to O(k log(n)) time very easily.
BUT the result that you are thinking about is Frederickson, G.N.: An Optimal Algorithm for Selection in a Min-Heap(?) that shows how to find the value of the kth smallest number in time O(k). Now you use the fact that a heap is a binary tree and start from the root and do a recursive search for every number that you find which is smaller than that largest. Then fill out the rest of your list with copies of the k'th smallest number.
In that search you will wind up looking at up to k-1 that are at most that size, and for some of them you will look at up to 2 children that are too large to bother with, for a maximum of 3k-3 elements. This makes the whole algorithm O(k).
That link died due to bitrot. Hopefully https://www.sciencedirect.com/science/article/pii/S0890540183710308 lasts longer.