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.