ヒープの構築

数学的基礎とデータ構造 (アルゴリズムイントロダクション)のp126付近。

use strict;
use warnings;

sub parent {
    my $i = shift;
    return int($i/2);
}

sub left {
    my $i = shift;
    return 2 * $i;
}

sub right {
    my $i = shift;
    return 2 * $i + 1;
}

sub heap_size {
    my $a = shift;
    my $length = @$a; # 配列をスカラーに代入すると長さが得られる
    return $length;
}

sub heap_print {
    sub heap_print_internal {
	my ($a, $i, $indent) = @_;
	if ($i <= @$a) {
	    print " " x $indent, @$a[$i-1], "\n";
	    &heap_print_internal($a, &left($i), $indent + 1);
	    &heap_print_internal($a, &right($i), $indent + 1);
	}
    }
    my $a = shift;
    &heap_print_internal($a, 1, 0);
}

sub max_heapify {
    my ($a, $i) = @_;
    my $l = &left($i);
    my $r = &right($i);
    my $largest = undef;
    if ($l <= heap_size($a) && @$a[$l -1] > @$a[$i -1]) {
	$largest = $l;
    } else {
	$largest = $i;
    }

    if ($r <= heap_size($a) && @$a[$r -1] > @$a[$largest -1]) {
	$largest = $r;
    }

    if ($largest != $i) {
        my $tmp = undef;
	# swap
	$tmp =  @$a[$i-1];
	@$a[$i-1] = @$a[$largest -1];
	@$a[$largest -1] = $tmp;
	
	max_heapify($a, $largest);
    }
}

sub build_max_heap {
    my $a = shift;
    foreach (reverse(1..int(@$a /2))) {
	max_heapify($a,$_);
    }
}

my @a = (4, 1, 3, 2, 16, 9, 10, 14, 8, 7);
&build_max_heap(\@a);
&heap_print(\@a);

これは簡単だなー。

/tmp% perl build_max_heap.pl
16
 14
  8
   2
   4
  7
   1
 10
  9
  3