bubbledown

Bubbledown is a term used in computer science to describe the process of restoring the heap property in a binary heap by moving a node downward within the tree. It typically occurs after removing the root element or after replacing the root with the last element during heap operations. In many sources the operation is called sift-down, sink, or heapify-down, and bubbledown is used interchangeably in some contexts.

Algorithmically, bubbledown operates on a heap stored in an array. For a node at index i (using 0-based indexing, left child is 2i+1 and right child is 2i+2), while i has at least one child: determine the child that should swap with i to maintain the heap property (the smaller child for a min-heap, the larger child for a max-heap). If the chosen child is more favorable than the current node, swap i with that child and continue from the child’s index; otherwise stop. In practice, the last element of the heap is often moved to the root before bubbling down begins.

Complexity and notes: Bubble-down runs in O(log n) time in a binary heap and typically O(1) extra space when the heap is stored in place. It is the counterpart to bubble-up (sift-up), which is used after insertions or key adjustments that violate the heap property. The concept extends to d-ary heaps as well, where the procedure may consider multiple children to determine the correct swap. Common applications include priority queues and heapsort.