ヒープ木
順位キューで挿入と探索をlogNで行いたいときに使う
挿入のときは最下層の一番左に挿入して補正 取り出すときは一番上から取得 => 最下層の一番左にあったものを上に付けて補正
を行うので常に完全バランスが取れて、左からノードが埋まっていく。
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 をする。