Kth Smallest Element Using Min Heap in DSA C - Time & Space Complexity

Time Complexity: Kth Smallest Element Using Min Heap

O(n + k log n)

Understanding Time Complexity

We want to understand how the time needed to find the kth smallest element using a min heap changes as the input size grows.

Specifically, how does the number of operations increase when the array size or k changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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) {
        int temp = arr[i]; arr[i] = arr[smallest]; arr[smallest] = temp;
        heapify(arr, n, smallest);
    }
}

int extractMin(int arr[], int *n) {
    int root = arr[0];
    arr[0] = arr[*n - 1];
    (*n)--;
    heapify(arr, *n, 0);
    return root;
}

int kthSmallest(int arr[], int n, int k) {
    // Build min heap
    for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);

    // Extract min k-1 times
    for (int i = 0; i < k - 1; i++) extractMin(arr, &n);

    return arr[0];
}

This code builds a min heap from an array and extracts the minimum element k-1 times to find the kth smallest element.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Heapify calls during building the heap and after each extraction.
• How many times: Heapify is called once for each non-leaf node during build (about n/2 times), and then k-1 times after each extraction.

How Execution Grows With Input

Building the heap takes time proportional to the number of elements, and each extraction involves heapify which depends on the heap height.

Input Size (n)	Approx. Operations
10, k=3	Build heap ~ 20 ops, Extract 2 times ~ 6 ops each
100, k=10	Build heap ~ 200 ops, Extract 9 times ~ 60 ops each
1000, k=100	Build heap ~ 2000 ops, Extract 99 times ~ 600 ops each

Pattern observation: Build heap grows roughly linearly with n, extraction grows with k times log n, so total grows with n plus k log n.

Final Time Complexity

Time Complexity: O(n + k log n)

This means the time grows linearly with the array size plus k times the logarithm of the array size.

Common Mistake

[X] Wrong: "Extracting the kth smallest element using a min heap always takes O(n log n) time because we do k extractions."

[OK] Correct: Actually, building the heap is O(n), and each extraction is O(log n), so total is O(n + k log n), which can be much faster if k is small.

Interview Connect

Understanding this time complexity helps you explain why using a min heap is efficient for finding the kth smallest element, a common problem in interviews.

Self-Check

"What if we used a max heap of size k instead of a min heap of size n? How would the time complexity change?"

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