読者です 読者をやめる 読者になる 読者になる

ヒープ条件の維持

Perl

数学的基礎とデータ構造 (アルゴリズムイントロダクション)の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