数学的基礎とデータ構造 (アルゴリズムイントロダクション)のp124付近。
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); print "left : ", $l, ", right : ", $r, "\n"; 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; } print '$largest : ', $largest, "\n"; 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); } } my @a = (16, 4, 10, 14, 7, 9, 3, 2, 8, 1); print "before : [", join(",",@a), "].\n"; print "=" x 30, "\n"; &max_heapify(\@a, 2); print "=" x 30, "\n"; print "after : [", join(",",@a), "].\n"; &heap_print(\@a);
実行結果。ツリーっぽく表示させるためのメソッドも用意してみた。
/tmp% perl max-heapify.pl before : [16,4,10,14,7,9,3,2,8,1]. ============================== left : 4, right : 5 $largest : 4 left : 8, right : 9 $largest : 9 left : 18, right : 19 $largest : 9 ============================== after : [16,14,10,8,7,9,3,2,4,1]. 16 14 8 2 4 7 1 10 9 3