it is clearly O(klogn). We are popping k times from a heap of size n.