[Originally posted by graham patterson]

Hi Andrew,

Well, I've worked my way right to the end of your truly superb book and gotten

every single code sample to work -- except one, so this is my last question on

this forum! Here goes: the original heap sort algorithm in chapter 17 works

fine, but I couldn't get the version using a recursive pushdown sub to work.

Here's what I have for the original:

#!/usr/bin/perl

use warnings;

use strict;

my @array = (7, 10, 5, 2, 6, 3, 1, 9, 4,

;

print "@array original

";

heap_sort(@array);

print "@array sorted

";

##### subs #####

sub heap_sort {

my $heap = @_;

unshift @$heap, scalar @_;

for (my $i = int($heap->[0] / 2); $i >= 1; $i--) {

pushdown($heap, $i);

}

for (my $i = $heap->[0]; $i >= 2; $i--) {

($heap->[1], $heap->[$i]) = ($heap->[$i], $heap->[1]);

# print "@array

"; # DEBUG

$heap->[0]--;

pushdown($heap, 1);

}

shift @$heap;

}

sub pushdown {

my ($heap, $i) = @_;

my $size = $heap->[0];

while ($i <= $size / 2) {

my $child = 2 * $i;

if ($child < $size and $heap->[$child] < $heap->[$child + 1]) {

$child++;

}

if ($heap->[$i] >= $heap->[$child]) { last; }

($heap->[$i], $heap->[$child]) = ($heap->[$child], $heap->[$i]);

$i = $child;

}

}

Now the above code works as advertised, giving output like this (with a print

statement added in the for loop as shown):

7 10 5 2 6 3 1 9 4 8 original

6 9 5 7 8 3 1 2 4 10

4 8 5 7 6 3 1 2 9 10

2 7 5 4 6 3 1 8 9 10

1 6 5 4 2 3 7 8 9 10

3 4 5 1 2 6 7 8 9 10

2 4 3 1 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10 sorted

But when I try the same code using the recursive version of the pushdown sub

from the solutions to the exercises elsewhere on this site, instead of the

original, the sort doesn't work. Here's what I have for the recursive sub

version:

sub pushdown {

my $i = shift;

my $l = 2 * $i;

my $r = $l + 1;

my $largest = 0;

if ($l <= $_[0] and $_[$l] > $_[$i]) {

$largest = $l;

} else {

$largest = $i;

}

if ($r <= $_[0] and $_[$r] > $_[$largest]) {

$largest = $r;

}

if ($largest != $i) {

($_[$largest], $_[$i]) = ($_[$i], $_[$largest]);

unshift @_, $i;

&pushdown;

}

}

and here's the output (again with a print statement added):

7 10 5 2 6 3 1 9 4 8 original

8 10 5 2 6 3 1 9 4 7

4 10 5 2 6 3 1 9 8 7

9 10 5 2 6 3 1 4 8 7

1 10 5 2 6 3 9 4 8 7

3 10 5 2 6 1 9 4 8 7

6 10 5 2 3 1 9 4 8 7

2 10 5 6 3 1 9 4 8 7

5 10 2 6 3 1 9 4 8 7

10 5 2 6 3 1 9 4 8 7

10 5 2 6 3 1 9 4 8 7 sorted

So it looks like the code is not correctly identifying the largest element and

moving it to the end, then the next largest to end -1, etc. I've spent ages

trying to think my way through the problem, stepped through the code using the

debugger, etc, but finally I have to admit defeat. Do I need to modify the

program in some way, or have I just mistyped something somewhere?

Thanks as always for your help,

Graham