Heap Extract Min or Max Bubble Down in DSA Typescript - Execution Trace

Concept Flow - Heap Extract Min or Max Bubble Down

Start: Extract root (min or max)

↓

Replace root with last element

↓

Remove last element from heap

↓

Set current index = 0

↓

Compare current with children

↓

Left child smaller/larger?

↓

Swap with smallest/largest child

↓

Update current index to swapped child

↓

Repeat until no swap needed

↓

Done

This flow shows how extracting the root from a heap replaces it with the last element, then bubbles that element down by swapping with its smaller (min-heap) or larger (max-heap) child until heap property is restored.

Execution Sample

DSA Typescript

function extractRoot(heap: number[]): number | null {
  if (heap.length === 0) return null;
  const root = heap[0];
  if (heap.length === 1) {
    heap.pop();
    return root;
  }
  heap[0] = heap.pop()!;
  bubbleDown(heap, 0);
  return root;
}

Extracts the root of the heap and restores heap property by bubbling down the new root.

Execution Table

Step	Operation	Heap Array	Pointer Changes	Visual State
1	Extract root (10)	[10, 15, 30, 40, 50, 100, 40]	root = 10	Array: [10, 15, 30, 40, 50, 100, 40] Tree: 10 / \ 15 30 / \ / \ 40 50 100 40
2	Replace root with last element (40)	[40, 15, 30, 40, 50, 100]	root replaced by last element 40	Array: [40, 15, 30, 40, 50, 100] Tree: 40 / \ 15 30 / \ / 40 50 100
3	Bubble down start at index 0	[40, 15, 30, 40, 50, 100]	current = 0	Current node: 40 at root
4	Compare children (15 and 30), smallest is 15 at index 1	[40, 15, 30, 40, 50, 100]	left child index=1, right child index=2	Left child 15 < current 40, right child 30 > 15
5	Swap current (40) with left child (15)	[15, 40, 30, 40, 50, 100]	swap indices 0 and 1	Array: [15, 40, 30, 40, 50, 100] Tree: 15 / \ 40 30 / \ / 40 50 100
6	Update current index to 1	[15, 40, 30, 40, 50, 100]	current = 1	Current node: 40 at index 1
7	Compare children (40 and 50), smallest is 40 at index 3	[15, 40, 30, 40, 50, 100]	left child index=3, right child index=4	Left child 40 < current 40? No (equal), right child 50 > 40
8	No swap needed, bubble down ends	[15, 40, 30, 40, 50, 100]	no swap	Heap property restored

💡 No swap needed at step 8, bubble down complete, heap property restored

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 6	After Step 8
heap	[10, 15, 30, 40, 50, 100, 40]	[40, 15, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]
current	N/A	0	0	1	1
root	10	10	10	10	10
swap indices	N/A	N/A	0 and 1	N/A	N/A

Key Moments - 3 Insights

Why do we replace the root with the last element before bubbling down?

Replacing the root with the last element keeps the heap complete (no gaps). Then bubbling down restores the heap order. See execution_table step 2 where root 10 is replaced by last element 40.

Why do we compare both children before swapping?

We must swap with the smallest child (min-heap) to maintain heap order. If we swap with the wrong child, heap property breaks. See step 4 where children 15 and 30 are compared before swapping.

When does the bubble down stop?

Bubble down stops when the current node is smaller than both children (min-heap), so no swap is needed. See step 8 where no swap occurs and bubble down ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which elements are swapped?

A 40 and 15

B 40 and 30

C 15 and 30

D No swap

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at step 5 in execution_table.

At which step does the bubble down process stop?

A Step 7

B Step 8

C Step 6

D Step 4

💡 Hint

Look for the step where 'No swap needed' and 'bubble down ends' in execution_table.

If the last element was smaller than both children, what would happen at step 4?

A Swap with left child

B Swap with right child

C No swap, bubble down ends

D Remove another element

💡 Hint

Refer to the comparison logic in execution_table step 4 and when bubble down stops.

Concept Snapshot

Heap Extract Min or Max Bubble Down:
- Remove root (min or max element)
- Replace root with last element
- Remove last element from heap
- Bubble down new root by swapping with smaller/larger child
- Repeat until heap property restored
- Maintains complete binary tree and heap order

Full Transcript

Heap extract operation removes the root element, which is the minimum in a min-heap or maximum in a max-heap. To keep the heap complete, the last element replaces the root. Then, the new root is bubbled down by comparing it with its children and swapping with the smaller (min-heap) or larger (max-heap) child if needed. This process repeats until the heap property is restored, meaning the current node is smaller (or larger) than its children. The execution table shows each step with the heap array, pointer changes, and visual tree state. Key moments clarify why replacement and comparisons are necessary and when bubbling down stops. The visual quiz tests understanding of swaps, stopping condition, and behavior if the last element is larger than children.

Practice

1. What is the main purpose of the bubble down operation in a min-heap after extracting the minimum element?

easy

A. To delete the last element in the heap

B. To insert a new element at the bottom of the heap

C. To swap the minimum element with the maximum element

D. To restore the heap property by moving the root element down to its correct position

Solution

1. Step 1: Understand extract-min operation

   When the minimum element (root) is removed, the last element replaces the root.

2. Step 2: Apply bubble down to restore heap

   The bubble down moves this element down the tree to restore the min-heap property.

3. Final Answer:

   To restore the heap property by moving the root element down to its correct position -> Option D

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap after removing root [OK]

Common Mistakes:

• Confusing bubble down with insertion
• Thinking bubble down swaps min and max
• Assuming bubble down deletes elements

2. Which of the following TypeScript code snippets correctly swaps two elements in a heap array during bubble down?

easy

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

B. const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp;

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

D. heap[i] = heap[j]; heap[j] = heap[i];

Solution

1. Step 1: Check valid swap syntax in TypeScript

   const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; uses a temporary variable to swap two elements correctly.

2. Step 2: Identify incorrect syntax in other options

   heap[i], heap[j] = heap[j], heap[i]; uses Python-style unpacking (invalid in TypeScript), C calls undefined function, D overwrites values incorrectly.

3. Final Answer:

   const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in TypeScript [OK]

Hint: Use temp variable for swapping in TypeScript [OK]

Common Mistakes:

• Using Python tuple swap syntax in TypeScript
• Calling undefined swap function
• Overwriting values without temp variable

3. Consider the min-heap array [2, 5, 3, 10, 7]. After extracting the minimum element and performing bubble down, what is the resulting heap array?

medium

A. [3, 5, 7, 10]

B. [3, 7, 5, 10]

C. [5, 7, 3, 10]

D. [7, 5, 3, 10]

Solution

1. Step 1: Remove root and replace with last element

   Remove 2, replace root with 7: [7, 5, 3, 10]

2. Step 2: Bubble down 7 to restore min-heap

   Compare 7 with children 5 and 3; swap with smallest child 3: [3, 5, 7, 10]

3. Final Answer:

   [3, 5, 7, 10] -> Option A

4. Quick Check:

   Extract min and bubble down result = [3, 5, 7, 10] [OK]

Hint: Replace root with last, then bubble down [OK]

Common Mistakes:

• Not replacing root with last element
• Swapping with wrong child during bubble down
• Forgetting to remove last element

4. The following TypeScript code attempts to bubble down an element in a max-heap but does not work correctly. What is the main bug?

function bubbleDown(heap: number[], i: number) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  let largest = i;

  if (left < heap.length && heap[left] > heap[largest]) {
    largest = left;
  }
  if (right < heap.length && heap[right] > heap[largest]) {
    largest = right;
  }

  if (largest !== i) {
    heap[i] = heap[largest];
    heap[largest] = heap[i];
    bubbleDown(heap, largest);
  }
}

medium

A. Swapping elements overwrites values incorrectly without a temporary variable

B. The indices for left and right children are calculated incorrectly

C. The recursive call should be bubbleUp instead of bubbleDown

D. The condition to check children is reversed for max-heap

Solution

1. Step 1: Analyze swap logic in code

   The swap uses heap[i] = heap[largest]; heap[largest] = heap[i]; which overwrites heap[i] before assigning heap[largest].

2. Step 2: Identify correct swap method

   Swapping requires a temporary variable to avoid overwriting values.

3. Final Answer:

   Swapping elements overwrites values incorrectly without a temporary variable -> Option A

4. Quick Check:

   Swap needs temp variable to avoid overwrite [OK]

Hint: Always use temp variable when swapping array elements [OK]

Common Mistakes:

• Overwriting values during swap without temp
• Confusing bubbleDown with bubbleUp
• Incorrect child index calculations

5. You have a max-heap represented by the array [50, 30, 40, 10, 20, 35]. After extracting the maximum element and performing bubble down, what is the final heap array?

hard

A. [35, 30, 40, 10, 20]

B. [40, 30, 20, 10, 35]

C. [40, 30, 35, 10, 20]

D. [30, 20, 35, 10, 40]

Solution

1. Step 1: Remove max (root) and replace with last element

   Remove 50, replace root with 35: [35, 30, 40, 10, 20]

2. Step 2: Bubble down 35 to restore max-heap

   Compare 35 with children 30 and 40; swap with largest child 40: [40, 30, 35, 10, 20]

3. Final Answer:

   [40, 30, 35, 10, 20] -> Option C

4. Quick Check:

   Extract max and bubble down result = [40, 30, 35, 10, 20] [OK]

Hint: Replace root with last, then bubble down largest child [OK]

Common Mistakes:

• Swapping with wrong child during bubble down
• Not removing last element after replacement
• Confusing min-heap bubble down with max-heap