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

Concept Flow - Kth Smallest Element Using Min Heap

Build Min Heap from array

↓

Repeat k-1 times: Extract Min

↓

Extract Min again

↓

Return extracted value as kth smallest

Build a min heap from the array, then remove the smallest element k times. The last removed element is the kth smallest.

Execution Sample

DSA Javascript

const kthSmallest = (arr, k) => {
  const heap = new MinHeap(arr);
  for (let i = 1; i < k; i++) heap.extractMin();
  return heap.extractMin();
};

This code builds a min heap from the array, extracts the smallest element k-1 times, then returns the kth smallest.

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 time)	[4, 7, 15, 10, 20]	Root 3 removed, last element 15 moved to root, heapify	4 -> 7 -> 15 -> 10 -> 20
3	Extract Min (2nd time)	[7, 10, 15, 20]	Root 4 removed, last element 20 moved to root, heapify	7 -> 10 -> 15 -> 20
4	Extract Min (3rd time, kth=3)	[10, 20, 15]	Root 7 removed, last element 15 moved to root, heapify	10 -> 20 -> 15

💡 After 3 extractions, the last extracted value 7 is the 3rd smallest element.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4
heap array	[7,10,4,3,20,15]	[3,7,4,10,20,15]	[4,7,15,10,20]	[7,10,15,20]	[10,20,15]
extracted values	[]	[]	[3]	[3,4]	[3,4,7]

Key Moments - 3 Insights

Why do we build the min heap first instead of sorting the array?

Building a min heap allows efficient extraction of the smallest element multiple times without sorting the entire array, as shown in Step 1 and subsequent extractions in the execution_table.

Why do we extract min k times instead of just once?

Each extraction removes the smallest element. Extracting k times ensures the kth smallest is the last extracted, as seen in Steps 2 to 4 in the execution_table.

What happens to the heap after each extraction?

After removing the root, the last element moves to root and heapify restores min heap property, shown by pointer changes and visual state in execution_table rows.

Visual Quiz - 3 Questions

Look at the execution_table, what is the heap array after the 2nd extraction?

A [3, 7, 4, 10, 20, 15]

B [4, 7, 15, 10, 20]

C [7, 10, 15, 20]

D [10, 20, 15]

💡 Hint

Check the 'Nodes in Heap' column at Step 3 in execution_table.

At which step is the kth smallest element extracted?

A Step 1

B Step 4

C Step 2

D Step 3

💡 Hint

Look at the 'Operation' column and note when k=3 extraction happens.

If k was 2 instead of 3, what would be the last extracted value?

A 4

B 7

C 3

D 10

💡 Hint

Refer to 'extracted values' in variable_tracker after Step 3.

Concept Snapshot

Kth Smallest Using Min Heap:
- Build min heap from array
- Extract min element k times
- Last extracted is kth smallest
- Heapify after each extraction
- Efficient for repeated smallest extraction

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 times. Each extraction removes the smallest element and re-heapifies the structure to maintain the min heap property. The last extracted element after k removals is the kth smallest element in the array. This method avoids sorting the entire array and is efficient for repeated smallest element retrievals.