#!/usr/bin/perl


 # Heapsort
 # Author: John Bryan, Jr.
 # Date:   August 30, 2006
 # Opens file, integers.txt, containing integers.
 # Sorts integers using Heapsort and writes sorted 
 # integers to screen.


 use strict;


 sub GetIntegers
 {
    my $c;
    $main::i=0;$main::j=0;$main::M=0;$main::k=0;$main::Number=0;
    $main::file ='integers.txt';
    open(INTS, $main::file);
    @main::integers1 = <INTS>;
    close(INTS);
    $main::M="$#main::integers1"+1;
    for ($c=0;$c<$main::M;$c++)
    {
       push(@main::integers,split(' ',$main::integers1[$c]));
    }
    $main::N="$#main::integers"+1;
    $main::Number=$main::N;
    print "\nThe integers to be sorted are\n";
    &PrintIntegers;
 }


 sub PrintIntegers
 {
    my $c;
    print("\n");
    for ($c=0;$c<$main::Number;$c++)
    {
      print ("$main::integers[$c]  ");
    }
 }


 sub BubbleDown
 {
    $main::j=$main::i;
    do
    {
       $main::k=$main::j;
       if(((2*$main::k+1)<$main::N)&&
          ($main::integers[2*$main::k+1]>$main::integers[$main::j]))
             {$main::j=2*$main::k+1;}
       if(((2*$main::k+2)<$main::N)&&
          ($main::integers[2*$main::k+2]>$main::integers[$main::j]))
             {$main::j=2*$main::k+2;}
       &Swap;
    }while($main::k!=$main::j);
 }


 sub HeapSort
 {
    my $r;
    for ($r=$main::N-1; $r>0; $r--)
    {
       $main::k=$r;
       $main::j=0;
       &Swap;
       $main::i=0;
       $main::N=$r;
       &BubbleDown;
    }
    print "\nThe sorted integers are\n";
    &PrintIntegers;
 }


 sub Swap
 {
    my $temp;
    $temp=$main::integers[$main::k];
    $main::integers[$main::k]=$main::integers[$main::j];
    $main::integers[$main::j]=$temp;
 }


 sub ConstructHeap
 {
    for ($main::i=$main::N-1; $main::i>=0; $main::i--)
       {&BubbleDown;}
 }


 &GetIntegers;
 &ConstructHeap;
 &HeapSort;