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.

Practice

1. What is the main purpose of the bubble up operation when inserting a new element into a max heap?

easy

A. To move the new element up until the heap property is restored

B. To move the new element down to the bottom of the heap

C. To remove the smallest element from the heap

D. To sort all elements in ascending order

Solution

1. Step 1: Understand heap property

   A max heap requires each parent to be greater than or equal to its children.

2. Step 2: Purpose of bubble up

   When a new element is added at the end, bubble up moves it up to restore the max heap property.

3. Final Answer:

   To move the new element up until the heap property is restored -> Option A

4. Quick Check:

   Bubble up fixes heap by moving element up [OK]

Hint: Bubble up moves new element up to fix heap [OK]

Common Mistakes:

• Thinking bubble up moves element down
• Confusing bubble up with removing elements
• Assuming bubble up sorts entire heap

2. Which of the following is the correct syntax to swap two elements at indices i and parentIndex in a JavaScript array heap during bubble up?

easy

A. [heap[i], heap[parentIndex]] = [heap[parentIndex], heap[i]];

B. heap.swap(i, parentIndex);

C. swap(heap[i], heap[parentIndex]);

D. heap[i], heap[parentIndex] = heap[parentIndex], heap[i];

Solution

1. Step 1: Identify JavaScript swap syntax

   JavaScript uses array destructuring to swap: [a, b] = [b, a];

2. Step 2: Apply to heap array

   Swapping heap[i] and heap[parentIndex] is done by [heap[i], heap[parentIndex]] = [heap[parentIndex], heap[i]];

3. Final Answer:

   [heap[i], heap[parentIndex]] = [heap[parentIndex], heap[i]]; -> Option A

4. Quick Check:

   Destructuring swap syntax = [heap[i], heap[parentIndex]] = [heap[parentIndex], heap[i]]; [OK]

Hint: Use array destructuring to swap in JS [OK]

Common Mistakes:

• Using Python-style swap syntax
• Calling undefined swap function
• Trying to use non-existent array method

3. Given the max heap array [50, 30, 40, 10, 20], what will be the heap array after inserting 45 and performing bubble up?

medium

A. [50, 45, 40, 10, 20, 30]

B. [50, 30, 40, 10, 20, 45]

C. [45, 30, 50, 10, 20, 40]

D. [50, 30, 45, 10, 20, 40]

Solution

1. Step 1: Insert 45 at the end

   Heap becomes [50, 30, 40, 10, 20, 45]

2. Step 2: Bubble up 45

   Parent index of 45 (index 5) is 2 (value 40). Since 45 > 40, swap them. New heap: [50, 30, 45, 10, 20, 40]

3. Final Answer:

   [50, 30, 45, 10, 20, 40] -> Option D

4. Quick Check:

   Bubble up swaps 45 with 40 [OK]

Hint: Insert at end, then swap up if bigger than parent [OK]

Common Mistakes:

• Not swapping after insertion
• Swapping with wrong parent index
• Assuming insertion sorts entire heap

4. Consider this bubble up code snippet for a max heap insertion:

while (i > 0 && heap[i] > heap[parentIndex]) {
  [heap[i], heap[parentIndex]] = [heap[parentIndex], heap[i]];
  i = parentIndex;
  parentIndex = Math.floor((i - 1) / 2);
}

What is the bug if parentIndex is not updated inside the loop?

medium

A. Syntax error due to missing semicolon

B. Heap property is restored correctly

C. Loop terminates prematurely after one swap because parentIndex never changes

D. The loop never runs because i is never updated

Solution

1. Step 1: Understand loop variables

   Inside the loop, after swap i = parentIndex, but if parentIndex is not updated, i now equals the unchanged parentIndex.

2. Step 2: Consequence of not updating parentIndex

   The condition heap[i] > heap[parentIndex] becomes heap[pos] > heap[pos] which is false, causing premature loop termination without full restoration.

3. Final Answer:

   Loop terminates prematurely after one swap because parentIndex never changes -> Option C

4. Quick Check:

   Without parentIndex update, i == parentIndex stops loop early [OK]

Hint: Always update parentIndex after swapping [OK]

Common Mistakes:

• Forgetting to update parentIndex
• Assuming i update is enough
• Ignoring loop condition effects

5. You have a min heap represented as [5, 10, 15, 20, 25]. You want to insert 12 and maintain the min heap property using bubble up. Which of the following sequences correctly shows the heap array after each bubble up swap?

medium

A. [5, 10, 15, 20, 25, 12] -> [5, 10, 15, 20, 25, 12]

B. [5, 10, 15, 20, 25, 12] -> [5, 10, 12, 20, 25, 15]

C. [5, 10, 15, 20, 25, 12] -> [5, 12, 15, 20, 25, 10]

D. [5, 10, 15, 20, 25, 12] -> [12, 10, 15, 20, 25, 5]

Solution

1. Step 1: Insert 12 at the end

   Heap becomes [5, 10, 15, 20, 25, 12]

2. Step 2: Bubble up 12

   Parent index of 12 (index 5) is 2 (value 15). Since 12 < 15, swap them. New heap: [5, 10, 12, 20, 25, 15]

3. Final Answer:

   [5, 10, 15, 20, 25, 12] -> [5, 10, 12, 20, 25, 15] -> Option B

4. Quick Check:

   Bubble up swaps 12 with 15 in min heap [OK]

Hint: In min heap, bubble up swaps if child < parent [OK]

Common Mistakes:

• Swapping with wrong parent
• Not swapping when child is smaller
• Confusing min heap with max heap rules