Skip to content

Instantly share code, notes, and snippets.

@hoelzro
Last active December 30, 2015 11:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hoelzro/7820243 to your computer and use it in GitHub Desktop.
Save hoelzro/7820243 to your computer and use it in GitHub Desktop.
Binary min heap in Perl 6
use v6;
class BinaryHeap {
has @!values;
method push($value) {
@!values.push: $value;
my int $current-index = @!values.end;
loop {
my int $parent-index = (($current-index + 1) / 2).floor - 1;
last if $parent-index < 0;
last if @!values[$parent-index] <= $value;
@!values[$current-index] = @!values[$parent-index];
@!values[$parent-index] = $value;
$current-index = $parent-index;
}
}
method pop {
my $result = @!values[0];
if @!values == 1 {
@!values.pop;
} else {
my $value = @!values.pop;
@!values[0] = $value;
my int $current-index = 0;
loop {
my int $left-index = ($current-index + 1) * 2 - 1;
my int $right-index = ($current-index + 1) * 2;
last if $left-index >= @!values;
my int $replacement-index;
if $right-index >= @!values {
$replacement-index = $left-index;
} else {
$replacement-index = @!values[$left-index] <= @!values[$right-index] ?? $left-index !! $right-index;
}
last if $value <= @!values[$replacement-index];
@!values[$current-index] = @!values[$replacement-index];
@!values[$replacement-index] = $value;
$current-index = $replacement-index;
}
}
$result
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment