Kth Smallest Element Using Min Heap in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the min heap size.

DSA C

int minHeapSize = [1];

Drag options to blanks, or click blank then click option'

Ak

B0

Cn

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing heap size to 0 or n instead of k.

Using 1 which is not related to k.

The min heap size should be initialized to k because we want to find the kth smallest element.

2fill in blank

medium

Complete the code to insert an element into the min heap.

DSA C

void insertMinHeap(int heap[], int* size, int value) {
    heap[*size] = value;
    int i = *size;
    (*size)++;
    while (i != 0 && heap[(i - 1) / 2] > heap[i]) {
        int temp = heap[i];
        heap[i] = heap[(i - 1) / 2];
        heap[(i - 1) / 2] = [1];
        i = (i - 1) / 2;
    }
}

Drag options to blanks, or click blank then click option'

Aheap[(i - 1) / 2]

Bvalue

Cheap[i]

Dtemp

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong variable for swapping.

Not swapping correctly causing infinite loop.

We swap the current element with its parent using the temporary variable 'temp'.

3fill in blank

hard

Fix the error in the code to heapify the min heap.

DSA C

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[[1]])
        smallest = left;
    if (right < size && heap[right] < heap[smallest])
        smallest = right;
    if (smallest != i) {
        int temp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = temp;
        minHeapify(heap, size, smallest);
    }
}

Drag options to blanks, or click blank then click option'

Ai

Bleft

Cright

Dsmallest

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with wrong index causing incorrect heap property.

Using smallest instead of i in first comparison.

We compare heap[left] with heap[i] to find the smallest element.

4fill in blank

hard

Fill both blanks to extract the minimum element from the min heap.

DSA C

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

Drag options to blanks, or click blank then click option'

A(*size)

B0

C1

D(*size) - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong index for last element.

Heapifying from wrong index.

We replace root with last element at index (*size) - 1 and heapify from root index 0.

5fill in blank

hard

Fill all three blanks to find the kth smallest element using the min heap.

DSA C

int kthSmallest(int arr[], int n, int k) {
    int heap[[1]];
    int size = 0;
    for (int i = 0; i < n; i++) {
        insertMinHeap(heap, &size, arr[i]);
    }
    int result = -1;
    for (int i = 0; i < [2]; i++) {
        result = extractMin(heap, &size);
    }
    return [3];
}

Drag options to blanks, or click blank then click option'

An

Bk

Cresult

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong heap size.

Extracting min wrong number of times.

Returning wrong variable.

Heap size is n to hold all elements, extract min k times, then return the last extracted value.

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