ヒープ木

順位キューで挿入と探索をlogNで行いたいときに使う

二分ヒープ - Wikipedia

挿入のときは最下層の一番左に挿入して補正 取り出すときは一番上から取得 => 最下層の一番左にあったものを上に付けて補正

を行うので常に完全バランスが取れて、左からノードが埋まっていく。

perlでのheap実装

# heap木

my @a = (7,  2, 3);
foreach ( @a ) {
    heap_insert($_);
}

my $ret;

while ( $ret = heap_remove() ) {
    print $ret. "\n";
}

my @heap;

sub heap_remove {

    return unless ( @heap );

    if ( @heap == 1 ) {
        return pop @heap;
    }

    my $top = $heap[0];
    $heap[0] = pop @heap;
    top_down(0);

    return $top;
}

sub heap_insert {
    my ($data) = @_;
    my $n = scalar @heap;
    $heap[$n] = $data;

    bottom_up($n);
}

sub bottom_up {
    my ($index) = @_;

    return if ( $index == 0 );

    my $parent_index = int ( ( $index + 1 ) / 2 ) - 1;
     if ( $heap[$index] > $heap[$parent_index] ) {

         @heap[$index, $parent_index] = @heap[$parent_index, $index]; # swap
         bottom_up($parent_index);
     }
 }

 sub top_down {
     my ($index) = @_;

     my $n = scalar @heap;

     my $l = ($index + 1) * 2 - 1;
     my $r = $l + 1;

     if ( $l < $n && $heap[$l] > $heap[$index] ) {
         @heap[$l, $index] = @heap[$index, $l];
         top_down($l);
     } elsif ( $r < $n && $heap[$r] > $heap[$index] ) {
         @heap[$r, $index] = @heap[$index, $r];
         top_down($r);
     }
 }

データは配列として格納する。 一つ上のノードにアクセスする場合は /2 一つ下のノードにアクセスする場合は *2 をする。