heap: fix heap_remove()

Remove should shuffle items in both directions, not just down. It is required, because `max` node could be not the actual maximum value in the tree. fix #1267 Signed-off-by: Fedor Indutny <[email protected]>
libuv · May 23, 2014 · e002340 · e002340
1 parent 70c4256
commit e002340
Showing 1 changed file with 7 additions and 0 deletions.
diff --git a/src/heap-inl.h b/src/heap-inl.h
@@ -227,6 +227,13 @@ HEAP_EXPORT(void heap_remove(struct heap* heap,
       break;
     heap_node_swap(heap, child, smallest);
   }
+
+  /* Walk up the subtree and check that each parent is less than the node
+   * this is required, because `max` node is not guaranteed to be the
+   * actual maximum in tree
+   */
+  while (child->parent != NULL && less_than(child, child->parent))
+    heap_node_swap(heap, child->parent, child);
 }
 
 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {