From 6074d5430effe9efb2a1c8486cabcfbcb8eafb63 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 23 May 2011 17:49:12 -0400 Subject: [PATCH] No need to rebalance heap for insertion Signed-off-by: Mathieu Desnoyers --- lib/prio_heap/prio_heap.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) diff --git a/lib/prio_heap/prio_heap.c b/lib/prio_heap/prio_heap.c index c987d5de..29af3033 100644 --- a/lib/prio_heap/prio_heap.c +++ b/lib/prio_heap/prio_heap.c @@ -158,8 +158,11 @@ int heap_insert(struct ptr_heap *heap, void *p) ptrs[pos] = ptrs[parent(pos)]; ptrs[parent(pos)] = tmp; pos = parent(pos); - /* rebalance */ - heapify(heap, pos); + /* + * No need to rebalance: if we are larger than + * our parent, we are necessarily larger than + * its other child. + */ } else { break; } -- 2.34.1