I was proposing to solve the problem originally stated. I thought that my description of how to solve it using a heap was fairly clear on that point by telling you when to start removing elements while still adding them.
I know. Just misinterpreted it. Sorry. One of my many moments of stupidity ;-)
I agree that until N is large (causing, eg, memory problems) or the comparison function is expensive, using sort will be faster. The heap solution outlined is helpful only for large N.
A good XS heap implementation would still win over sort with small N. It's just a C vs Perl issue speedwise.