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

Heap Insert: Upward Bubbling Concept

Learn how insertion maintains heap property by bubbling new elements upward through parent comparisons.

Heap Insert: Upward Bubbling Concept

What you'll learn: How to maintain heap order when inserting a new element by comparing and swapping it upward with its parents.

The Core Idea

When you insert a new element into a binary heap, you can't just place it anywhere—you must preserve both the complete binary tree shape and the heap order property. The insertion process follows two steps:

  1. Place the new element at the next available position (the leftmost open spot at the bottom level, maintaining the complete tree shape)
  2. "Bubble up" or "percolate up" the new element by repeatedly comparing it with its parent and swapping if needed

How Upward Bubbling Works

Think of bubbles rising in water—lighter bubbles naturally float upward. Similarly, in a min-heap, smaller values "bubble up" toward the root; in a max-heap, larger values bubble up.

After placing the new element at the end of the heap array:

  • Compare it with its parent (using the parent-child index formulas you learned)
  • If the heap order is violated (child smaller than parent in min-heap, or larger in max-heap), swap them
  • Repeat this comparison-and-swap process moving upward until either:
    • The heap order property is satisfied, or
    • You reach the root (no parent to compare)

Example Walkthrough

Inserting 3 into a min-heap: [5, 10, 15, 20, 25]

  1. Place 3 at index 5: [5, 10, 15, 20, 25, 3]
  2. Compare 3 with parent 10 (at index 2): violates min-heap! Swap → [5, 3, 15, 20, 25, 10]
  3. Compare 3 with parent 5 (at index 0): violates min-heap! Swap → [3, 5, 15, 20, 25, 10]
  4. Now 3 is at the root—done!

Key Takeaway: Heap insertion maintains the heap order property by bubbling the new element upward through successive parent comparisons and swaps until it finds its correct position.