Heap Insert Operation Bubble Up in DSA Typescript - Execution Trace

Concept Flow - Heap Insert Operation Bubble Up

Add new element at end of array

↓

Compare new element with parent

↓

Swap with parent

↓

Move pointer to parent

↩Back to Compare

Insert element at the end, then compare and swap with parent until heap property is restored.

Execution Sample

DSA Typescript

heap = [10, 15, 30, 40, 50, 100, 40]
insert(8)
// Bubble up to restore heap

Insert 8 into min-heap and bubble it up to maintain heap order.

Execution Table

Step	Operation	Array State	Pointer (index)	Action	Visual State
1	Insert 8 at end	[10, 15, 30, 40, 50, 100, 40, 8]	7 (new element)	Add 8 at index 7	Array: [10, 15, 30, 40, 50, 100, 40, 8]
2	Compare with parent	[10, 15, 30, 40, 50, 100, 40, 8]	7 (8) vs 3 (40)	8 < 40 → Swap	Swap index 7 and 3
3	After swap	[10, 15, 30, 8, 50, 100, 40, 40]	3 (8)	Move pointer to 3	Array: [10, 15, 30, 8, 50, 100, 40, 40]
4	Compare with parent	[10, 15, 30, 8, 50, 100, 40, 40]	3 (8) vs 1 (15)	8 < 15 → Swap	Swap index 3 and 1
5	After swap	[10, 8, 30, 15, 50, 100, 40, 40]	1 (8)	Move pointer to 1	Array: [10, 8, 30, 15, 50, 100, 40, 40]
6	Compare with parent	[10, 8, 30, 15, 50, 100, 40, 40]	1 (8) vs 0 (10)	8 < 10 → Swap	Swap index 1 and 0
7	After swap	[8, 10, 30, 15, 50, 100, 40, 40]	0 (8)	Move pointer to 0	Array: [8, 10, 30, 15, 50, 100, 40, 40]
8	Compare with parent	[8, 10, 30, 15, 50, 100, 40, 40]	0 (8) has no parent	Stop bubbling up	Heap property restored

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

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	Final
heap array	[10, 15, 30, 40, 50, 100, 40]	[10, 15, 30, 40, 50, 100, 40, 8]	[10, 15, 30, 8, 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]
pointer index	N/A	7	3	1	0	0
pointer value	N/A	8	8	8	8	8

Key Moments - 3 Insights

Why do we compare the new element with its parent during bubble up?

Because the heap property depends on parent-child order. We check if the new element is smaller than its parent to decide if swapping is needed (see execution_table steps 2, 4, 6).

What happens when the pointer reaches the root during bubble up?

There is no parent to compare with, so the bubble up stops (see execution_table step 8). This means the heap property is restored.

Why do we swap elements during bubble up instead of just inserting at the end?

Inserting at the end may break the heap order. Swapping with parents moves the new element up to restore the heap property (see execution_table steps 2, 4, 6).

Visual Quiz - 3 Questions

Look at the execution table, what is the heap array after step 5?

A [10, 8, 30, 15, 50, 100, 40, 40]

B [10, 15, 30, 8, 50, 100, 40, 40]

C [8, 10, 30, 15, 50, 100, 40, 40]

D [10, 15, 30, 40, 50, 100, 40, 8]

💡 Hint

Check the 'Array State' column at step 5 in the execution_table.

At which step does the pointer reach the root and stop bubbling up?

A Step 6

B Step 8

C Step 7

D Step 5

💡 Hint

Look for the step where the pointer index is 0 and no parent exists in execution_table.

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

A It would bubble up to the root.

B It would swap once with the parent.

C No swaps would happen; insertion stops immediately.

D It would cause an error.

💡 Hint

Refer to the comparison logic in execution_table steps 2, 4, 6 where swaps happen only if new element is less than parent.

Concept Snapshot

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

Full Transcript

This visual trace shows how inserting a new element into a min-heap works by adding it at the end of the array and then bubbling it up. The bubble up compares the new element with its parent and swaps if the new element is smaller. This process repeats until the new element reaches the root or no swap is needed, restoring the heap property. The execution table tracks each step, showing array states and pointer movements. Key moments clarify why comparisons and swaps happen and when the process stops. The quiz tests understanding of array states and stopping conditions.