Kth Smallest Element Using Min Heap in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Extraction

What is the output of the following C code that finds the 3rd smallest element using a min heap?

DSA C

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

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

void minHeapify(int heap[], int size, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && heap[left] < heap[smallest])
        smallest = left;
    if (right < size && heap[right] < heap[smallest])
        smallest = right;
    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        minHeapify(heap, size, smallest);
    }
}

int extractMin(int heap[], int *size) {
    if (*size <= 0) return -1;
    int root = heap[0];
    heap[0] = heap[*size - 1];
    (*size)--;
    minHeapify(heap, *size, 0);
    return root;
}

int kthSmallest(int arr[], int n, int k) {
    int *heap = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        heap[i] = arr[i];

    for (int i = n / 2 - 1; i >= 0; i--)
        minHeapify(heap, n, i);

    int size = n;
    int result = -1;
    for (int i = 0; i < k; i++)
        result = extractMin(heap, &size);

    free(heap);
    return result;
}

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

A 3

B 4

C 7

D 10

💡 Hint

Remember the min heap always extracts the smallest element first.

The min heap extracts elements in ascending order. The 1st smallest is 3, 2nd is 4, and 3rd is 7.

❓ Predict Output

intermediate

Resulting Heap After Building Min Heap

What is the state of the heap array after building the min heap from this array: [12, 3, 5, 7, 19]?

DSA C

#include <stdio.h>

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

void minHeapify(int heap[], int size, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && heap[left] < heap[smallest])
        smallest = left;
    if (right < size && heap[right] < heap[smallest])
        smallest = right;
    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        minHeapify(heap, size, smallest);
    }
}

int main() {
    int heap[] = {12, 3, 5, 7, 19};
    int size = 5;
    for (int i = size / 2 - 1; i >= 0; i--) {
        minHeapify(heap, size, i);
    }
    for (int i = 0; i < size; i++) {
        printf("%d ", heap[i]);
    }
    return 0;
}

A 3 7 5 19 12

B 3 5 12 7 19

C 3 5 7 12 19

D 3 7 5 12 19

💡 Hint

Start heapifying from the last non-leaf node upwards.

After heapify, the smallest element is at root (index 0). The array represents the min heap in level order.

🧠 Conceptual

advanced

Understanding Min Heap Extraction

When extracting the minimum element from a min heap, which step is NOT performed?

A Sort the entire heap array

B Decrease the heap size by one

C Heapify the root to maintain min heap property

D Replace the root with the last element in the heap

💡 Hint

Think about what heapify does versus sorting.

Extracting min involves replacing root with last element, reducing size, and heapifying root. Sorting entire heap is not done.

❓ Predict Output

advanced

Output After Multiple ExtractMin Calls

Given the min heap array [2, 4, 3, 7, 9, 10], what is the output after two extractMin operations?

DSA C

#include <stdio.h>

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

void minHeapify(int heap[], int size, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && heap[left] < heap[smallest])
        smallest = left;
    if (right < size && heap[right] < heap[smallest])
        smallest = right;
    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        minHeapify(heap, size, smallest);
    }
}

int extractMin(int heap[], int *size) {
    if (*size <= 0) return -1;
    int root = heap[0];
    heap[0] = heap[*size - 1];
    (*size)--;
    minHeapify(heap, *size, 0);
    return root;
}

int main() {
    int heap[] = {2, 4, 3, 7, 9, 10};
    int size = 6;
    int first = extractMin(heap, &size);
    int second = extractMin(heap, &size);
    printf("%d %d\n", first, second);
    return 0;
}

A 2 4

B 2 3

C 3 4

D 4 7

💡 Hint

ExtractMin returns the root each time and then heapifies.

First extractMin returns 2, then heapify makes 3 the root. Second extractMin returns 3, but after heapify 4 becomes root. So second extracted is 4.

🧠 Conceptual

expert

Time Complexity of Kth Smallest Using Min Heap

What is the time complexity of finding the kth smallest element in an array of size n using a min heap built from the entire array?

A O(k log k)

B O(n + k log n)

C O(n log k)

D O(n log n)

💡 Hint

Consider heap building and k extractions separately.

Building a min heap takes O(n). Extracting min k times takes O(k log n). Total is O(n + k log n).

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