New answers tagged heaps
2
Delete-max is $O(\log n)$, so you have $O(n) + k O(\log n)$ which is $O(n)$ for fixed $k$. But if $k$ is not fixed, it can be up to $\frac{n}{2}$ (if it's greater, just use a min-heap instead of a max-heap), and $O(n) + \frac{n}{2} O(\log n) = O(n \log n)$.
In fact, if there was some tricky way to do what you want, you would solve sorting in $O(n)$, not ...
1
Building a heap is O(n).
Taking the first item from a heap and then re-arranging things so it is a heap again is O (log n), and since you need to do this n time is O (n log n).
Of course you can just take one element of the heap after the other in O(n), but they won't be in sorted order. And building a heap can be done in O(n) because you add n/2 items to ...
Top 50 recent answers are included
