[Heap]- after removing a node, should you run siftDown for all nodes or just the root?

user_14903506 0
Viewed 41

I have seen implementations of binary heap where after removal of a node, heapifyDown/siftDown (whatever the author names it) is run only on the root to re-heapify the tree, and some where siftDown is run iteratively on all items from the bottom up to the root.

I assume that before one would remove a node, the tree of N items is already built/heapified and satisfies min- or max-heap property. If that's true - what's the point of trying to run siftDown on nodes (N//2)-1 [first non-leaf node with indexing from 0] and up, let alone ALL nodes from the end- instead of sifting only the root? Is that a poor implementation, or am I missing something?

*Extra question: are there any reasons for removing nodes from the middle of a min- or max-heap? I would think extracting the root, or maybe the last element, is most important. Is it ever being done in practice when heap is used as data structure?

binary-heap heap data-structures
1 Answers

There’s no need to run heapifyDown / siftDown on all elements after removing the minimum. That will indeed fix the heap, but it takes time O(n) to do this, which is pretty slow and defeats the purpose of having a binary heap. Instead, the traditional algorithm is to swap the last element of the heap to the top, then call heapifyDown / siftDown on it. This takes time O(log n), which is much faster than rebuilding the whole heap.

As for removing nodes from the middle of the heap - that’s fairly uncommon but not unheard of. What’s more common is, for graph algorithms like Dijkstra’s shortest paths algorithm or Prim’s minimum spanning tree algorithm, to take an element in the heap and reduce its priority (in a min heap) or increase it (in a max heap). This can be done by locating the element in the heap, reducing its priority, and then calling heapifyUp / siftUp on it to restore the heap property.

user_5015570
Related