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.