• Make sure Heap::Simple::XS is used if you care about speed for this kind of operation.
• Use the (default) scalar element type if that is good enough. It's the fastest of the available element types.
• Use the max_count option if you only want an already known last m elements. This will save a lot of compares. In this case it also saves the extract loop.

You can also add the dirty option. Heap::Simple::XS will then use direct numeric compares instead of calling perl's >. This breaks overload and ties though. That way the Heap::Simple solution is about twice as fast as sort. The break-even is somewhere in the ten thousands of elements.

The resulting code looks something like this:

use List::Util qw(shuffle);
use POSIX qw(ceil);
use Heap::Simple::XS;

my @list = shuffle(0..1e6); 
my $h = Heap::Simple::XS->new(max_count => ceil(@list/2),
                              dirty => 1);
$h->insert(@list);
print $h->extract_top;
[download]

This doesn't change the fact that for even quite big lists sort is just faster for this kind of problem. Heaps are mainly for when you need to know the smallest element at many points in time while the set of elements keeps changing. Or indeed for some cases where compare is very expensive, but even then there are better ways to do it with less compares if you just want the median.

PS: Heap::Simple already uses special code to make an insert of many elements at once faster than repeatedly inserting one element. You seem to hint at an even faster algorithm but I don't see how to use Tarjan's algorithm for that. Can you give me a reference ?