Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re: Heap sorting in perl

by Abigail-II (Bishop)
on Apr 07, 2003 at 11:20 UTC ( #248560=note: print w/ replies, xml ) Need Help??


in reply to Re: Re: Heap sorting in perl
in thread Heap sorting in perl

Yeah, whatever. Here's a modification of the program. Give the number of elements to extract as a command line argument, and the elements to extract from on STDIN. It assumes that there are enough elements on STDIN.

#!/usr/bin/perl use strict; use warnings; my @heap; my $M = @ARGV ? shift : 10; sub heapify; sub heapify { my $idx = shift; my $max = $idx; for my $try (2 * $idx + 1, 2 * $idx + 2) { $max = $try if $try < @heap && $heap [$try] > $heap [$max] } return if $max == $idx; @heap [$idx, $max] = @heap [$max, $idx]; heapify $max; } sub extract_max { return unless @heap; my $min = $heap [0]; my $tmp = pop @heap; if (@heap) { $heap [0] = $tmp; heapify 0; } return $min; } # First load the heap with initial data. for (1 .. $M) { push @heap => scalar <>; } chomp @heap; # # Heapify it. # for (my $i = int (@heap / 2); $i --;) { heapify $i; } # # Deal with the rest. # while (<>) { chomp; next if $_ >= $heap [0]; # It's too large. $heap [0] = $_; heapify 0; } my @result; push @result => extract_max while @heap; @result = reverse @result; print "@result\n"; __END__

The running time of this is O (N log k), using O (k) memory.

Abigail


Comment on Re: Heap sorting in perl
Download Code
Re: Re: Heap sorting in perl
by Anonymous Monk on Apr 07, 2003 at 11:40 UTC
    Every so often I really wish that I had learned more about algorithms. This is one of those times.

    Beautiful.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://248560]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (7)
As of 2014-07-25 02:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (167 votes), past polls