siftup

Siftup, also called percolate up or bubble up, is an operation used in heap-based data structures to restore the heap property after an insertion or a key decrease. In a binary heap stored in an array, a newly inserted element is appended at the end. The siftup procedure compares the element with its parent; if the heap property is violated (for example, in a min-heap if the element is smaller than its parent, or in a max-heap if it is larger), the two are swapped. The element then takes the place of its parent, and the process repeats with the new parent index until the element is at a position where the property holds or the root is reached. The result is that the path from the insertion point to the root is corrected, ensuring the heap remains valid.

Time complexity for siftup in a binary heap is O(log n), since the height of the heap grows logarithmically with the number of elements. The operation typically requires O(1) extra space, as it moves a single element up the tree in place. Siftup is the counterpart to sift-down (percolate down), which moves an element downward to restore the heap during deletions and sometimes key adjustments in a min-heap or max-heap. Variants exist for different heap implementations, such as d-ary heaps, but the core idea remains moving the element upward until the heap condition is satisfied. In practice, siftup is a fundamental primitive in priority queues and heap-based sorting algorithms, enabling efficient insertion and key adjustments with logarithmic cost.