Kth Smallest Element Using Min Heap in DSA Typescript - Execution Trace

Concept Flow - Kth Smallest Element Using Min Heap

Build Min Heap from array

↓

Extract min element k-1 times

↓

Heap root is kth smallest

↓

Return root value

Build a min heap from the array, then remove the smallest element k-1 times. The root after these removals is the kth smallest.

Execution Sample

DSA Typescript

function kthSmallest(arr: number[], k: number): number {
  const minHeap = new MinHeap(arr);
  for (let i = 1; i < k; i++) {
    minHeap.extractMin();
  }
  return minHeap.getMin();
}

Find kth smallest by building a min heap and extracting min k-1 times, then returning the root.

Execution Table

Step	Operation	Nodes in Heap	Pointer Changes	Visual State
1	Build Min Heap from [7, 10, 4, 3, 20, 15]	[3, 7, 4, 10, 20, 15]	Heapify rearranged nodes	3 -> 7 -> 4 -> 10 -> 20 -> 15
2	Extract Min (1st extraction)	[4, 7, 15, 10, 20]	Root 3 removed, last element 20 moved to root, heapify down	4 -> 7 -> 15 -> 10 -> 20
3	Extract Min (2nd extraction)	[7, 10, 15, 20]	Root 4 removed, last element 20 moved to root, heapify down	7 -> 10 -> 15 -> 20
4	Return root as 3rd smallest	[7, 10, 15, 20]	No pointer change	7 -> 10 -> 15 -> 20

💡 After 2 extractions (k-1), root is kth smallest element 7

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
Heap Array	[7,10,4,3,20,15]	[3,7,4,10,20,15]	[4,7,15,10,20]	[7,10,15,20]	[7,10,15,20]
Heap Size	6	6	5	4	4
Extracted Elements	[]	[]	[3]	[3,4]	[3,4]
Current Root	7	3	4	7	7

Key Moments - 3 Insights

Why do we extract min k-1 times instead of k times?

Because after removing the smallest element k-1 times, the root of the heap is the kth smallest. Extracting k times would remove the kth smallest itself.

Why does the heap change after each extraction?

After removing the root, the last element moves to root and heapify rearranges nodes to maintain min heap property, as shown in steps 2 and 3.

Why is the initial heap root 3 and not 4 or 7?

Heapify rearranges the array so the smallest element is at the root, which is 3 in step 1, ensuring min heap property.

Visual Quiz - 3 Questions

Look at the execution table, what is the heap root after the first extraction?

A 3

B 4

C 7

D 15

💡 Hint

Check Step 2 in execution_table under 'Current Root' and 'Visual State'

At which step does the heap size become 4?

A After Step 3

B After Step 2

C After Step 1

D After Step 4

💡 Hint

Look at variable_tracker row 'Heap Size' for changes after each step

If k was 2 instead of 3, what would be the kth smallest element returned?

A 3

B 7

C 4

D 10

💡 Hint

Refer to execution_table rows for extractions and root values after k-1 removals

Concept Snapshot

Kth Smallest Using Min Heap:
- Build min heap from array
- Extract min element k-1 times
- Root after extractions is kth smallest
- Extraction removes smallest and heapify restores order
- Time: O(n + k log n) for heap operations

Full Transcript

To find the kth smallest element using a min heap, first build a min heap from the input array. This organizes the data so the smallest element is at the root. Then, extract the minimum element k-1 times, each time removing the root and re-heapifying to maintain the heap property. After these extractions, the root of the heap is the kth smallest element. This method efficiently finds the kth smallest without sorting the entire array.