Course contentsShow
← Computer Science
Lesson 590 of 2,87214. Heaps and Priority QueuesFree lesson

Downward Bubbling (Heapify-Down)

Learn the sift-down process that restores heap property after root removal.

Downward Bubbling (Heapify-Down)

You'll learn how to restore heap order property after removing the root element by pushing a misplaced node down to its correct position.

The Problem After Root Removal

When you extract the maximum (or minimum) from a heap, you replace the root with the last element in the array to maintain the complete binary tree shape. This replacement element is usually not in the right place—it's probably too small (in a max-heap) or too large (in a min-heap) to be at the root. The heap order property is now broken.

The Sift-Down Process

Downward bubbling (also called heapify-down or sift-down) fixes this by repeatedly swapping the misplaced element with its larger child (in a max-heap) or smaller child (in a min-heap) until it finds its proper position.

Here's how it works:

  1. Start at the root (or wherever the violation occurred)
  2. Compare the current node with its children
  3. If heap property is satisfied, stop
  4. Otherwise, swap with the appropriate child (larger child in max-heap, smaller in min-heap)
  5. Move down to that child's position and repeat

Analogy

Imagine a corporate hierarchy where someone unqualified suddenly becomes CEO. They "bubble down" by swapping positions with their most qualified direct report, then continue swapping downward through the ranks until they reach a level matching their competence.

Why It Works

Unlike upward bubbling (which always compares with one parent), downward bubbling must check both children and choose the right one to swap with. This ensures the heap property is maintained throughout the entire subtree.

Key Takeaway: Heapify-down restores heap order after root removal by repeatedly swapping a misplaced node with its more extreme child (largest in max-heap, smallest in min-heap) until the heap property is satisfied or the node becomes a leaf.