in reply to Heap sorting in perl
#!/usr/bin/perl use strict; use warnings; my @heap; sub heapify; sub heapify { my $idx = shift; my $min = $idx; for my $try (2 * $idx + 1, 2 * $idx + 2) { $min = $try if $try < @heap && $heap [$try] < $heap [$min] } return if $min == $idx; @heap [$idx, $min] = @heap [$min, $idx]; heapify $min; } sub extract_min { return unless @heap; my $min = $heap [0]; my $tmp = pop @heap; if (@heap) { $heap [0] = $tmp; heapify 0; } return $min; } # # First argument the number of smallest elements to be returned. # Then the list to find the elements in. # sub smallest { my $k = shift; @heap = @_; for (my $i = int (@heap / 2); $i ;) { heapify $i; } my @result; push @result => extract_min while @heap && $k ; @result; } __END__
The running time of this is O (N + k log N), where N is the size of the set, and k the number of elements to be returned.
Abigail


Replies are listed 'Best First'.  

Re: Re: Heap sorting in perl
by Anonymous Monk on Apr 06, 2003 at 23:59 UTC  
by AbigailII (Bishop) on Apr 07, 2003 at 00:15 UTC  
by Anonymous Monk on Apr 07, 2003 at 03:40 UTC  
by AbigailII (Bishop) on Apr 07, 2003 at 11:20 UTC  
by Anonymous Monk on Apr 07, 2003 at 11:40 UTC  
by Aristotle (Chancellor) on Apr 07, 2003 at 08:49 UTC  
by Anonymous Monk on Apr 07, 2003 at 11:33 UTC 
In Section
Seekers of Perl Wisdom