/s

Actually if you RTFS a little more carefully you will see that 1) it never sorts the list (ever) 2) the only thing that gets sorted is the priorities array (which consists only of the n priority levels present) and 3) the only time it does this sort is when either a new (previously unknown) priority level is added or a priority level needs to be deleted as there are no more items of this priority present in the heap. It checks for the presence of a priority level via a hash key (rather than searching the whole priority array as a further speed hack.....

sub add {
   # blah
   unless (exists $self->{'.queue'}->{$priority}) {
       $self->{'.queue'}->{$priority} = ();
       $self->_sort_priorities;
   }
[download]

cheers

tachyon

s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print

"Actually if you RTFS a little more carefully"...

Had you PTFP, you might have realized that the link went nowhere -- at least it was a "not found" for me. You're right that I didn't read your code very carefully, but now that I have, I'm guessing it doesn't do what the original poster wanted. Or more accurately, your benchmark doesn't reflect its being used in the way he would use it, since it only uses a single priority. Try this instead:

use Priority;
my $q = new Priority;
my $time = time;
$q->add(1,$_) for 1..1000000;
$q->pop for 1..1000000;
print "Did a million in ",time - $time, " seconds";
[download]

/s