I was thinking through this problem. The solution I would have come up with would have been similar, but to use two balanced binary search trees instead of heaps (similar to a Java SortedSet or something). This seems to give an overall runtime of O(n log k) which might be slightly improved over the two heaps solution.
At each step, we effectively do the same thing, expect for the max and min now take O(log k) and the linear search for the node to be removed is swapped for the tree lookup at O(log k).
I was wondering if anyone had any thoughts about solving this problem in this way.