Kth Smallest Element Using Min Heap in DSA C

Mental Model

A min heap always keeps the smallest element at the top, so by removing the smallest element k times, we get the kth smallest.

Analogy: Imagine a line of people sorted by height but only knowing who is shortest at the front. Each time the shortest person leaves, the next shortest moves up. After k removals, the last person who left is the kth shortest.

Min Heap Array Representation:
[ 2, 5, 8, 10, 15 ]
Index:  0  1  2   3   4
Top (smallest) is at index 0

Dry Run Walkthrough

Input: array: [7, 10, 4, 3, 20, 15], k=3

Goal: Find the 3rd smallest element in the array using a min heap

Step 1: Build min heap from array

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

Why: Heapify arranges elements so smallest is at root for easy access

Step 2: Extract min (remove root) first time

[4, 7, 15, 10, 20]

Why: Remove smallest element (3), heap adjusts to keep min at root

Step 3: Extract min second time

[7, 10, 15, 20]

Why: Remove next smallest (4), heap adjusts again

Step 4: Extract min third time

[10, 20, 15]

Why: Remove third smallest (7), this is the kth smallest element

Result:

Heap after 3 extractions: [10, 20, 15]
3rd smallest element: 7

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] < arr[smallest])
        smallest = left;

    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        heapify(arr, n, smallest); // heapify subtree
    }
}

int extractMin(int arr[], int *n) {
    if (*n <= 0) return -1; // empty heap
    int root = arr[0];
    arr[0] = arr[*n - 1];
    (*n)--;
    heapify(arr, *n, 0); // restore heap property
    return root;
}

void buildMinHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i); // build heap from bottom up
    }
}

int kthSmallest(int arr[], int n, int k) {
    buildMinHeap(arr, n); // step 1: build min heap
    int result = -1;
    for (int i = 0; i < k; i++) {
        result = extractMin(arr, &n); // extract min k times
    }
    return result;
}

int main() {
    int arr[] = {7, 10, 4, 3, 20, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int result = kthSmallest(arr, n, k);
    printf("%dth smallest element is %d\n", k, result);
    return 0;
}

buildMinHeap(arr, n);

build min heap so smallest element is at root

result = extractMin(arr, &n);

extract min element k times to reach kth smallest

heapify(arr, *n, 0);

restore heap property after removing root

Output

3th smallest element is 7

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each extraction takes O(log n) repeated k times

Space: O(1) because the heap is built in-place without extra space

vs Alternative: Sorting the array takes O(n log n), which is slower than building a heap and extracting k times when k is small

Edge Cases

k is larger than array size

extractMin returns -1 indicating no kth smallest element

DSA C

if (*n <= 0) return -1;

array has one element and k=1

returns the single element correctly

DSA C

buildMinHeap and extractMin handle single element heap

array contains duplicate elements

duplicates are treated normally, kth smallest counts duplicates

DSA C

heapify compares values normally without special handling

When to Use This Pattern

When you need the kth smallest element and want better than full sort, use a min heap to efficiently extract the smallest elements one by one.

Common Mistakes

Mistake: Not rebuilding or heapifying after extracting min, so heap property breaks
Fix: Call heapify after each extraction to maintain min heap structure

Summary

Finds the kth smallest element by building a min heap and extracting the smallest element k times.

Use when you want kth smallest without sorting the entire array.

The smallest element is always at the root of a min heap, so repeated extraction gives kth smallest.

Practice

1. What is the main idea behind finding the kth smallest element using a min heap?

easy

A. Sort the array and pick the element at index k

B. Build a max heap and extract the maximum element k times

C. Build a min heap from the array and extract the minimum element k times

D. Use a hash map to count frequencies and find the kth smallest

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the root, so extracting the root gives the smallest element.

2. Step 2: Extract minimum k times

   By extracting the root k times, we get the kth smallest element at the last extraction.

3. Final Answer:

   Build a min heap and extract minimum k times -> Option C

4. Quick Check:

   Min heap root extraction = kth smallest element [OK]

Hint: Extract min from min heap k times to get kth smallest [OK]

Common Mistakes:

• Using max heap instead of min heap
• Sorting array instead of using heap
• Extracting min less or more than k times

2. Which of the following is the correct way to initialize a min heap in C using the standard library?

easy

A. Use make_heap with default comparator

B. Use priority_queue<int> directly

C. Use priority_queue<int, vector<int>, less<int>>

D. Use priority_queue<int, vector<int>, greater<int>>

Solution

1. Step 1: Identify min heap syntax in C++ STL

   To create a min heap, use priority_queue with greater<int> comparator.

2. Step 2: Check options

   priority_queue<int, vector<int>, greater<int>> uses greater<int> which creates a min heap. priority_queue<int> directly, the option with less<int>, and make_heap with default comparator all create max heaps.

3. Final Answer:

   Use priority_queue with greater comparator -> Option D

4. Quick Check:

   Min heap = priority_queue with greater comparator [OK]

Hint: Use greater comparator for min heap in priority_queue [OK]

Common Mistakes:

• Using default priority_queue which is max heap
• Confusing less and greater comparators
• Using make_heap without comparator

3. What will be the output of the following C code snippet to find the 3rd smallest element using a min heap?

int arr[] = {7, 10, 4, 3, 20, 15};
int n = 6, k = 3;
// Build min heap from arr
// Extract min k times
// Print last extracted element
// Assume min heap functions work correctly

medium

A. 3

B. 7

C. 4

D. 10

Solution

1. Step 1: Sort elements mentally or extract min

   Sorted array: [3, 4, 7, 10, 15, 20]. Extract min 3 times: 3, 4, 7.

2. Step 2: The 3rd extracted min is the 3rd smallest

   The 3rd smallest element is 7.

3. Final Answer:

   7 -> Option B

4. Quick Check:

   3rd smallest = 7 [OK]

Hint: Extract min k times; last extracted is kth smallest [OK]

Common Mistakes:

• Picking the 2nd or 4th extracted element
• Confusing kth smallest with kth largest
• Not building min heap correctly

4. Identify the error in the following code snippet that attempts to find the 2nd smallest element using a min heap:

int arr[] = {5, 3, 8, 1, 2};
int k = 2;
// Build min heap from arr
for (int i = 0; i <= k; i++) {
    extractMin();
}
print last extracted element;

medium

A. Loop runs one extra time; should be i < k

B. Min heap not built correctly

C. ExtractMin function returns max element

D. Array indexing error

Solution

1. Step 1: Analyze loop condition

   The loop runs from 0 to k inclusive, so it runs k+1 times, extracting one extra element.

2. Step 2: Correct loop to run exactly k times

   Loop should run while i < k to extract min exactly k times.

3. Final Answer:

   Loop runs one extra time; should be i < k -> Option A

4. Quick Check:

   Extract min exactly k times = loop i < k [OK]

Hint: Loop from 0 to less than k for k extractions [OK]

Common Mistakes:

• Using <= k causing extra extraction
• Not building min heap before extraction
• Confusing extractMin with extractMax

5. Given an array arr = {12, 3, 5, 7, 19}, write the steps to find the 4th smallest element using a min heap and explain why this method is efficient compared to sorting the entire array.

hard

A. Build min heap, extract min 4 times; efficient because heap operations are O(log n) each

B. Sort array and pick 4th element; more efficient than heap

C. Build max heap and extract max 4 times; efficient for kth smallest

D. Use linear search to find 4th smallest; faster than heap

Solution

1. Step 1: Build a min heap from the array

   Insert all elements into a min heap so the smallest element is at the root.

2. Step 2: Extract the minimum element 4 times

   Each extraction removes the smallest element. The 4th extraction gives the 4th smallest element.

3. Step 3: Efficiency explanation

   Building a heap takes O(n), each extraction O(log n), total O(n + k log n) which is efficient for large arrays compared to O(n log n) sorting.

4. Final Answer:

   Build min heap, extract min 4 times; efficient because heap operations are O(log n) each -> Option A

5. Quick Check:

   Min heap extraction = kth smallest efficiently [OK]

Hint: Heap extraction is faster than full sorting for kth element [OK]

Common Mistakes:

• Using max heap for kth smallest
• Sorting entire array unnecessarily
• Using linear search which is slower