# -*- mode: cperl6; -*- # 2011 Perl 6 Coding Contest # Edgar Gonzàlez i Pellicer # Heap module Heap; # Min heap class MinHeap is export { has Pair @!data; # Empty? method empty() { return !@!data; } # Size method size() { return @!data.elems; } # Top method top() { if @!data { return @!data[0]; } else { return; } } # Pop method pop() { # Which is the size given +@!data { # Empty when 0 { # Nothing } # One element when 1 { # Just remove it pop(@!data); } # More default { # Take the last, and move it to the head @!data[0] = pop(@!data); # Position and children my $p = 0; my $l = 1; my $r = 2; # Sink it while $l < @!data { if $r < @!data { # Two children if @!data[$p].key > @!data[$l].key || @!data[$p].key > @!data[$r].key { # Must sink if @!data[$l].key < @!data[$r].key { # Float left @!data[$p, $l] = @!data[$l, $p]; $p = $l; } else { # Float right @!data[$p, $r] = @!data[$r, $p]; $p = $r; } } else { # Stop last; } } else { # One child ($l) if @!data[$p].key > @!data[$l].key { # Must sink -> Float left @!data[$p, $l] = @!data[$l, $p]; $p = $l; } else { # Stop last; } } # Next children $l = 2 * $p + 1; $r = $l + 1; } } } # OK return; } # Push method push(Int $key, $value) { # Add it @!data.push(($key => $value)); # Position my $p = @!data.elems - 1; # Float it while $p > 0 { # Parent my $pp = $p div 2; if @!data[$pp].key > @!data[$p].key { # Float @!data[$p, $pp] = @!data[$pp, $p]; $p = $pp; } else { # Stop last; } } # OK return; } }