Perl 堆排序

看了算法导论堆排序，用Perl 实现一下，具体原理不解释，做个记录。

代码：

@a = map {int(rand 100)} 1..20;

sub build_heap{
     my $length = $#_;
     for(my $i = $length>>1; $i >= 0; $i--){
          heapnify(@_,$length,$i);
     }
}

sub heapnify{
     #~ $x++; #use it to trace how much times the procedure was run
     my ($array,$index) = @_;
    
     my $max = $array->[$index];
     my $tmp = $index;
     my $left = left($index);
     my $right = right($index);
    
     if($left <= $length && $array->[$left] > $max){
          $max = $array->[$left];
          $tmp = $left;
     }
     if($right <= $length && $array->[$right] > $max){
          $max = $array->[$right];
          $tmp = $right;
     }
    
     if($tmp != $index){
          ($array->[$index],$array->[$tmp]) = ($array->[$tmp],$array->[$index]);
          heapnify($array,$tmp) if $tmp <= $length>>1;
     }
}

sub left      { ($_[0]<<1) + 1 }
sub right     { left(@_) + 1 }

sub max_heap{
     build_heap(@_);
     @_[0,-1] = @_[-1,0];
     for(my $i=$#_-1;$i>0;$i--){
          heapnify(@_,$i,0);
          @_[0,$i] = @_[$i,0];
     }
}

max_heap(@a);
print "@an";