Heap Insert Operation Bubble Up in DSA Javascript - Execution Trace

Concept Flow - Heap Insert Operation Bubble Up

Insert new element at end of array

↓

Compare with parent node

↓

Swap with parent

↓

Move pointer to parent

↩Back to compare

Insert the new element at the end, then repeatedly swap it with its parent if smaller, moving up until heap property is restored.

Execution Sample

DSA Javascript

function bubbleUp(heap, index) {
  while (index > 0) {
    let parent = Math.floor((index - 1) / 2);
    if (heap[index] >= heap[parent]) break;
    [heap[index], heap[parent]] = [heap[parent], heap[index]];
    index = parent;
  }
}

This code moves the newly inserted element up the heap until the min-heap property is restored.

Execution Table

Step	Operation	Index	Parent Index	Heap Array State	Pointer Movement	Visual State
1	Insert 8 at end	7	3	[10, 15, 30, 40, 50, 100, 40, 8]	New element at index 7	Array: [10, 15, 30, 40, 50, 100, 40, 8] Tree: 10 / \ 15 30 / \ / \ 40 50 100 40 8 ← new node
2	Compare 8 with parent 40	7	3	[10, 15, 30, 40, 50, 100, 40, 8]	8 < 40 → swap	Swapping 8 (index 7) with parent 40 (index 3)
3	Move pointer to parent index 3	3	1	[10, 15, 30, 8, 50, 100, 40, 40]	Pointer moves to index 3	Tree after swap: 10 / \ 15 30 / \ / \ 8 50 100 40
4	Compare 8 with parent 15	3	1	[10, 15, 30, 8, 50, 100, 40, 40]	8 < 15 → swap	Swapping 8 (index 3) with parent 15 (index 1)
5	Move pointer to parent index 1	1	0	[10, 8, 30, 15, 50, 100, 40, 40]	Pointer moves to index 1	Tree after swap: 10 / \ 8 30 / \ / \ 15 50 100 40
6	Compare 8 with parent 10	1	0	[10, 8, 30, 15, 50, 100, 40, 40]	8 < 10 → swap	Swapping 8 (index 1) with parent 10 (index 0)
7	Move pointer to parent index 0	0	-	[8, 10, 30, 15, 50, 100, 40, 40]	Pointer moves to index 0 (root)	Tree after swap: 8 / \ 10 30 / \ / \ 15 50 100 40
8	Compare 8 with parent (none, index 0)	0	-	[8, 10, 30, 15, 50, 100, 40, 40]	At root, stop bubble up	Bubble up ends as pointer is at root

💡 Pointer reached root (index 0), no parent to compare, bubble up stops

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
index	-	7	3	3	1	1	0	0
parent	-	3	3	1	1	0	0	-
heap	[10,15,30,40,50,100,40]	[10,15,30,40,50,100,40,8]	[10,15,30,8,50,100,40,40]	[10,15,30,8,50,100,40,40]	[10,8,30,15,50,100,40,40]	[10,8,30,15,50,100,40,40]	[8,10,30,15,50,100,40,40]	[8,10,30,15,50,100,40,40]

Key Moments - 3 Insights

Why do we swap the new element with its parent only if it is smaller?

Because in a min-heap, parents must be smaller or equal to their children. The execution_table rows 2, 4, and 6 show swaps only happen when the child (new element) is smaller than the parent, restoring heap order.

Why does the bubble up stop when the pointer reaches index 0?

Index 0 is the root and has no parent. The execution_table row 8 shows that when index is 0, there is no parent to compare, so the bubble up stops.

What happens to the heap array after each swap?

The swapped elements exchange positions, as seen in the heap array state in execution_table rows 3, 5, and 7. This moves the new element up the tree to maintain heap property.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of the parent node before swapping?

A 15

B 8

C 10

D 30

💡 Hint

Check the 'Parent Index' and 'Heap Array State' columns at step 4 in execution_table.

At which step does the bubble up operation stop?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look for the step where the pointer is at index 0 and no further swaps occur in execution_table.

If the inserted element was 35 instead of 8, how would the bubble up change?

A No swaps would occur; bubble up stops immediately.

B Swaps would occur until the root.

C Only one swap would occur.

D The element would be inserted at the root directly.

💡 Hint

35 < 40 (parent at index 3), so one swap to index 3; then 35 >= 15 (parent at index 1), stop. Compare with steps 1-4 in execution_table.

Concept Snapshot

Heap Insert Bubble Up:
- Insert new element at end of heap array
- Compare with parent node
- If new element < parent, swap
- Move pointer to parent index
- Repeat until root or no swap needed
- Restores min-heap property

Full Transcript

The heap insert operation adds a new element at the end of the heap array. Then it compares this element with its parent. If the new element is smaller, it swaps places with the parent. This process repeats, moving the element up the tree, until it reaches the root or finds a parent smaller or equal to it. This ensures the min-heap property is maintained. The execution table shows each step, the heap array state, and pointer movements. The variable tracker records index and parent changes. Key moments clarify why swaps happen only when the child is smaller and why the bubble up stops at the root. The visual quiz tests understanding of these steps.

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