Heap Insert Operation Bubble Up in DSA Javascript

Mental Model

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

Analogy: Imagine adding a new kid to a line where shorter kids must stand in front. The new kid joins at the back and then moves forward until everyone is in the right order by height.

Heap as array:
[10, 15, 20, 17, 25]
Insert 13 at end:
[10, 15, 20, 17, 25, 13]
Indexes:
 0   1   2   3   4   5
↑                   (new element at index 5)

Dry Run Walkthrough

Input: heap: [10, 15, 20, 17, 25], insert value 13

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

Step 1: Insert 13 at the end of the heap array

[10, 15, 20, 17, 25, 13]

Why: New element must be added at the end before fixing the heap

Step 2: Compare 13 with its parent 20 at index 2; since 13 < 20, swap them

[10, 15, 13, 17, 25, 20]

Why: Smaller child should move up to maintain min-heap property

Step 3: Now 13 is at index 2; compare with parent 15 at index 1; 13 < 15, swap them

[10, 13, 15, 17, 25, 20]

Why: Smaller child should move up to maintain min-heap property

Step 4: Now 13 is at index 1; compare with parent 10 at index 0; 13 > 10, stop bubbling up

[10, 13, 15, 17, 25, 20]

Why: Heap property is restored; no more swaps needed

Result:

[10, 13, 15, 17, 25, 20]

Annotated Code

DSA Javascript

class MinHeap {
  constructor() {
    this.heap = [];
  }

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

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

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

// Driver code
const heap = new MinHeap();
heap.heap = [10, 15, 20, 17, 25];
heap.insert(13);
heap.printHeap();

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

Add new value at the end of the heap array

let index = this.heap.length - 1;

Start bubbling up from the last inserted element

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

Find parent index of current node

if (this.heap[index] < this.heap[parentIndex]) {

Check if child is smaller than parent to maintain min-heap

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

Swap child and parent to move smaller value up

index = parentIndex; // move up

Update index to parent's position to continue bubbling

else { break; }

Stop if heap property is restored

Output

10, 13, 15, 17, 25, 20

Complexity Analysis

Time: O(log n) because in worst case the new element moves up the height of the heap, which is log n

Space: O(1) because the operation modifies the heap in place without extra space

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

Edge Cases

Insert into empty heap

Element is added as root without bubbling

DSA Javascript

while (index > 0) {

Insert element larger than all existing elements

Element stays at the end, no swaps occur

DSA Javascript

else { break; }

Insert element smaller than root

Element bubbles all the way up to root

DSA Javascript

index = parentIndex;

When to Use This Pattern

When you need to add an 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 during bubble up
Fix: Assign index = parentIndex after swap to continue bubbling up

Mistake: Comparing child with wrong parent index
Fix: Calculate parent index as Math.floor((index - 1) / 2)

Summary

It adds a new element to a heap and moves it up until the heap order is correct.

Use it when inserting into a heap to keep the heap property intact.

The key is to swap the new element with its parent while it is smaller, moving it up step by step.