Construct a heap, which takes $O(n)$ time. Then call \method {removeMinElement} $k$ times, which takes $O(k \log n)$ time.