diff --git a/lemon/pairing_heap.h b/lemon/pairing_heap.h
--- a/lemon/pairing_heap.h
+++ b/lemon/pairing_heap.h
@@ -266,6 +266,8 @@
         minimum = container[minimum].child;
       }
 
+      if (minimum >= 0) container[minimum].left_child = false;
+
       --num_items;
     }