Implement the heap properly

1 files changed, 34 insertions, 16 deletions

diff --git a/challenge-018/e-choroba/perl5/ch-2.pl b/challenge-018/e-choroba/perl5/ch-2.pl
index dfa59b0bd6..27c913ee38 100755
--- a/challenge-018/e-choroba/perl5/ch-2.pl
+++ b/challenge-018/e-choroba/perl5/ch-2.pl
@@ -30,15 +30,11 @@ use feature qw{ say };
 
     my $i = 1;
     sub insert_with_priority {
-        my ($self, $element, $priority, $counter) = @_;
-        push @$self, [$element, $priority, ($counter // ++$i)];
+        my ($self, $element, $priority) = @_;
+        push @$self, [$element, $priority, ++$i];
         my $i = $#$self;
         my $p = int(($i - 1) / 2);
-        while ($p >= 0
-               && ($self->[$p][PRIORITY] < $self->[$i][PRIORITY]
-                   || ($self->[$p][PRIORITY] == $self->[$i][PRIORITY]
-                       && $self->[$p][COUNTER] > $self->[$i][COUNTER]))
-        ) {
+        while ($p >= 0 && $self->_compare($p, $i)) {
             @$self[$i, $p] = @$self[$p, $i];
             $i = $p;
             $p = int(($i - 1) / 2);
@@ -48,11 +44,33 @@ use feature qw{ say };
     sub pull_highest_priority_element {
         my ($self) = @_;
         my $element = shift(@$self)->[ELEMENT];
-        my $new = ref($self)->new;
-        $new->insert_with_priority(@$_) for @$self;
-        $_[0] = $new;
+        unshift @$self, pop @$self if @$self;
+        $self->_adjust(0);
         return $element
     }
+
+    sub _compare {
+        my ($self, $p1, $p2) = @_;
+        my $c = $self->[$p1][PRIORITY] <=> $self->[$p2][PRIORITY];
+        return $c == -1
+               || $c == 0 && $self->[$p1][COUNTER] > $self->[$p2][COUNTER]
+    }
+
+    sub _adjust {
+        my ($self, $pos) = @_;
+        if (my @children
+                = sort {
+                    ($self->[$a][PRIORITY] <=> $self->[$b][PRIORITY])
+                    || ($self->[$b][COUNTER] <=> $self->[$a][COUNTER])
+                } grep defined $self->[$_],
+                2 * $pos + 1, 2 * $pos + 2
+        ) {
+            if ($self->_compare($pos, $children[-1])) {
+                @$self[$pos, $children[-1] ] = @$self[$children[-1], $pos];
+                $self->_adjust($children[-1]);
+            }
+        }
+    }
 }
 
 use Test::More tests => 2 + 2 * 14;
@@ -65,17 +83,17 @@ for my $class (qw(My::Queue::Priority::Array My::Queue::Priority::Heap)) {
         for [a => 10], [b => 4], [c => 2], [d=>8], [e => 4], [f => 3];
     ok ! $q->is_empty;
 
-    is $q->pull_highest_priority_element, 'a', $class.$#$q;
+    is $q->pull_highest_priority_element, 'a';
     ok ! $q->is_empty;
-    is $q->pull_highest_priority_element, 'd', $class.$#$q;
+    is $q->pull_highest_priority_element, 'd';
     ok ! $q->is_empty;
-    is $q->pull_highest_priority_element, 'b', $class.$#$q;
+    is $q->pull_highest_priority_element, 'b';
     ok ! $q->is_empty;
-    is $q->pull_highest_priority_element, 'e', $class.$#$q;
+    is $q->pull_highest_priority_element, 'e';
     ok ! $q->is_empty;
-    is $q->pull_highest_priority_element, 'f', $class.$#$q;
+    is $q->pull_highest_priority_element, 'f';
     ok ! $q->is_empty;
-    is $q->pull_highest_priority_element, 'c', $class.$#$q;
+    is $q->pull_highest_priority_element, 'c';
     ok $q->is_empty;
 }