[scarmig]

You can solve it with two heaps, which don't need to maintain a complete order. Or selection algorithms, as in the sibling comment (asymptotically better).