siftdown

Siftdown, also written sift-down, is a heap operation used to restore the heap property by moving a node downward through a binary heap. It is one of the fundamental sifting procedures used to maintain the ordering invariant in array-based heaps after certain updates, such as removing the root or replacing it with the last element.

In a min-heap, the heap property requires that every node is less than or equal to its children. Siftdown works by repeatedly comparing the current node with its children and swapping it with the smaller child if that child is smaller than the current node. This process continues until the current node is less than or equal to both children or it reaches a leaf. In a max-heap, the analogous operation swaps with the larger child when necessary. For an array-based binary heap with 0-based indexing, the left and right children of a node at index i are at indices 2i+1 and 2i+2, respectively.

Siftdown is commonly used after removing the root element from a heap or after moving the last element to the root, to restore the heap order. It is also employed during heap sort and in the implementation of priority queues that rely on a heap structure. The time complexity of siftdown is O(log n), where n is the number of elements in the heap, since the operation traverses at most one level per step. The space complexity is O(1) beyond the input heap.

In programming libraries, siftdown appears as an internal helper in heap implementations. For example, Python’s heapq module includes an internal _siftdown function that performs this operation to restore the heap after insertions or removals. Variants exist for different heap architectures, such as d-ary heaps, but the core idea remains moving a misplaced node downward to restore the heap invariant.