Heap Insert Operation Bubble Up in DSA Typescript

Mental Model

When adding a new number to a heap, we put it at the end and then move it up to keep the heap rules.

Analogy: Imagine adding a new card to a pile where bigger cards must be on top. You place the card at the bottom and then swap it up until it fits the order.

       10
      /  \
     5    3
    / 
   2  
  ↑ (new value here at the end)

Dry Run Walkthrough

Input: heap: [10, 5, 3, 2], insert value 6

Goal: Add 6 to the heap and move it up until the heap property is restored

Step 1: Insert 6 at the end of the array

[10, 5, 3, 2, 6 ↑]

Why: New value must start at the end before moving up

Step 2: Compare 6 with its parent 5, swap because 6 > 5

[10, 6 ↑, 3, 2, 5]

Why: 6 is bigger than parent, so swap to keep max-heap order

Step 3: Compare 6 with new parent 10, no swap because 6 < 10

[10, 6 ↑, 3, 2, 5]

Why: 6 is smaller than parent, so stop bubbling up

Result:

[10, 6, 3, 2, 5] with heap property restored

Annotated Code

DSA Typescript

class MaxHeap {
  heap: number[] = [];

  insert(value: number) {
    this.heap.push(value); // add at end
    this.bubbleUp(); // fix heap
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index] <= this.heap[parentIndex]) break; // stop if heap property ok
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]]; // swap
      index = parentIndex; // move up
    }
  }

  printHeap() {
    console.log(this.heap.join(', '));
  }
}

// Driver code
const heap = new MaxHeap();
heap.heap = [10, 5, 3, 2];
heap.insert(6);
heap.printHeap();

this.heap.push(value); // add at end

Add new value at the end of the heap array

while (index > 0) {

Keep bubbling up until we reach the root

const parentIndex = Math.floor((index - 1) / 2);

Find parent index to compare

if (this.heap[index] <= this.heap[parentIndex]) break;

Stop if current value is not bigger than parent

[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];

Swap current value with parent to move up

index = parentIndex;

Update index to parent's position for next iteration

Output

10, 6, 3, 2, 5

Complexity Analysis

Time: O(log n) because the new value moves up at most the height of the heap

Space: O(1) because we only use a few variables and swap in place

vs Alternative: Compared to rebuilding the heap from scratch (O(n)), bubbling up is faster for single insertions

Edge Cases

Insert into empty heap

Value is added as root without bubbling

DSA Typescript

while (index > 0) {

Insert value smaller than all existing values

Value stays at the end, no swaps

DSA Typescript

if (this.heap[index] <= this.heap[parentIndex]) break;

Insert value larger than root

Value bubbles all the way to root

DSA Typescript

index = parentIndex;

When to Use This Pattern

When you need to add a new element to a heap and keep it ordered, use bubble up to restore heap order efficiently.

Common Mistakes

Mistake: Not updating the index after swapping, causing infinite loop
Fix: Set index = parentIndex after swap to continue bubbling up

Mistake: Swapping even when the child is smaller or equal to parent
Fix: Add condition to break loop if child <= parent

Summary

It adds a new value to the heap and moves it up to keep the heap order.

Use it when inserting elements into a heap to maintain the max-heap property.

The key is to swap the new value with its parent until it fits the heap rules.