BrowserUk,
I have already shared this with you on my scratch but I would like to leave it here as well for posterity purposes. It turns out that even without the overhead of function calls, a pure perl heap still doesn't compete with the binary search and splice. As tye pointed out in the CB as I was lamenting, count opcodes. My guess is that perl has very optimized C under the covers using memcpy and what not making it superior to a home grown heap.

I do want to point out that some of the complexity in the example below is because the heap has been special cased to this specific problem (limiting size). A general purpose implementation would be more powerful though less complex due to abstraction. This means it would also be slower.

#!/usr/bin/perl
use strict;
use warnings;
use Time::HiRes qw/gettimeofday tv_interval/;

my %hash  = construct_hash();
my ($cnt, $top_n, @heap, %known) = (0, int((keys %hash) * .10), (), ()
+);

my $beg = [gettimeofday];
while (1) {
    my ($max_key, $max_pos) = ('', undef);

    while (my ($key, $val) = each %hash) {

        # Skip entries we already have assigned a value too
        next if defined $val;

        # If we know the value of this key, assign it and move one
        if (exists $known{$key}) {
            $hash{$key} = $known{$key};
            next;
        }

        # Record where the key is inserted
        my $new_pos;

        # Check to see if heap is full
        if (@heap == $top_n) {
            # Key is already bigger than the top-n most key
            next if $key gt $max_key;

            # Insert the value in the previous maximum position
            ($heap[$max_pos], $new_pos) = ($key, $max_pos);

            # Find new max key and pos
            $max_key = '';
            my $beg = $max_pos % 2 ? (($max_pos - 1) / 2) : (($max_pos
+ - 2) / 2); 
            for ($beg .. $#heap) {
                ($max_key, $max_pos) = ($heap[$_], $_) if $heap[$_] gt
+ $max_key;
            }
        }
        else {
            push @heap, $key;
            $new_pos = $#heap;
            ($max_key, $max_pos) = ($key, $#heap) if $key gt $max_key;
        }

        # Bubble up
        my $parent_pos = $new_pos % 2 ? ($new_pos - 1) / 2 : ($new_pos
+ - 2) / 2; 
        while ($heap[$new_pos] lt $heap[$parent_pos] && $parent_pos > 
+-1) {
            $max_pos = $new_pos if $heap[$parent_pos] eq $max_key;
            ($heap[$new_pos], $heap[$parent_pos], $new_pos) = ($heap[$
+parent_pos], $heap[$new_pos], $parent_pos);
            $parent_pos = $new_pos % 2 ? ($new_pos - 1) / 2 : ($new_po
+s - 2) / 2; 
        }
    }
    last if ! @heap;
    %known = ();
    #@heap = sort @heap;
    #$known{$_} = ++$cnt for @heap;
    while (@heap) {
        my $key;
        if (@heap == 1 || @heap == 3) {
            $key = shift @heap;
        }
        elsif (@heap == 2) {
            $key = $heap[0] lt $heap[1] ? (shift @heap) : (pop @heap);
        }
        else {
            # Record the top item
            $key = $heap[0];

            # Replace the root with the last item from the last level 
            $heap[0] = pop @heap;

            # Bubble down
            my $cur_pos = 0;
            my $child_pos = $heap[1] lt $heap[2] ? 1 : 2;
            while ($heap[$cur_pos] gt $heap[$child_pos]) {
                ($heap[$cur_pos], $heap[$child_pos], $cur_pos) = ($hea
+p[$child_pos], $heap[$cur_pos], $child_pos);
                my ($l_pos, $r_pos) = ((($cur_pos * 2) + 1), (($cur_po
+s * 2) + 2));
                last if $l_pos > $#heap;
                if ($r_pos > $#heap) {
                    $child_pos = $l_pos;
                    next;
                }
                $child_pos = $heap[$l_pos] lt $heap[$r_pos] ? $l_pos :
+ $r_pos; 
            }
        }
        $known{$key} = ++$cnt;
    }
}
my $elapsed = tv_interval($beg, [gettimeofday]);
my $per = sprintf("%.7f", $elapsed / $cnt);
print "Took $elapsed seconds for $cnt items ($per per item)\n";

sub construct_hash {
    my $items = $ARGV[0] || 100;
    my $str = 'a';
    my %hash = map {$str++ => undef} 1 .. $items;
    return %hash;
}
[download]