ヒープソート - うらでぃみーる通信 @Wiki

use strict;
use warnings;
 
my $LIST_SIZE ||= 20;
my @heap;
 
for(my $i = 0; $i < $LIST_SIZE; $i++){
    $heap[$i] = int($i);
}
 
#ランダムに並び替える
srand;
for (my $i = @heap; --$i; ) {
  my $j = int rand ($i + 1);
  next if $i == $j;
  @heap[$i, $j] = @heap[$j, $i];
}
 
# 1個目はダミー
my @g_heap = (-1);
 
print_array(\@heap);   # 実行前
&heapsort(\@heap);
print_array(\@heap);   # 実行後
 
sub heapsort{
    my $array = shift;
    &insertheap($array);
    for(my $i = 0; $i < scalar(@$array); $i++){
        $array->[$i] = &get_root;
    }
}
 
sub insertheap{
    my $array = shift;
    for(my $i = 0; $i < scalar(@$array); $i++){
        push @g_heap, $array->[$i];
        upheap($#g_heap);
    }
}
 
sub upheap{
    my $index = shift;
    my $tmp = $g_heap[$index];
    while( ($index > 1) && ($g_heap[int($index / 2)] > $tmp)){
        $g_heap[$index] = $g_heap[int($index / 2)];
        $index = int($index / 2);
    }
    $g_heap[$index] = $tmp;
}
 
sub get_root{
    my $tmp;
    if( scalar(@g_heap) < 1){
        print "ヒープが空です";
        exit;
    }
    $tmp = $g_heap[1];
    $g_heap[1] = $g_heap[$#g_heap];
 
    pop @g_heap;
 
    &downheap;
    return $tmp;
}
 
sub downheap{
 
    if(scalar(@g_heap) < 2){
        return;
    }
 
    my $tmp = $g_heap[1];
 
    my $i = 1;
 
    while($i <= int($#g_heap / 2)){
        my $j = $i * 2;
 
        if( ($j + 1 <= $#g_heap) && ($g_heap[$j] > $g_heap[$j + 1]) ){
            $j++;
        }
 
        if($tmp <= $g_heap[$j]){
            last;
        }
 
        $g_heap[$i] = $g_heap[$j];
        $i = $j;
    }
    $g_heap[$i] = $tmp;
}
 
sub print_array{
    my $ref_array = shift;
    for my $i(@$ref_array){
        print "$i ";
    }
    print "\n";
}