Kth Smallest Element Using Min Heap in DSA C - Build from Scratch

Kth Smallest Element Using Min Heap

📖 Scenario: Imagine you have a list of numbers representing the scores of players in a game. You want to find the kth smallest score to see who is just above the others.

🎯 Goal: Build a program that uses a min heap to find the kth smallest element in an array of integers.

📋 What You'll Learn

Create an array called arr with the exact values: 7, 10, 4, 3, 20, 15

Create an integer variable called k and set it to 3

Implement a min heap using an array and functions to build the heap and extract the minimum

Use the min heap to find and print the kth smallest element

💡 Why This Matters

🌍 Real World

Finding the kth smallest or largest element is useful in ranking systems, statistics, and real-time data analysis.

💼 Career

Understanding heaps and selection algorithms is important for software engineers working on performance-critical applications and data processing.

1

Create the array of numbers

Create an integer array called arr with the values 7, 10, 4, 3, 20, 15 and an integer variable n that stores the size of the array.

DSA C

int arr[] = {7, 10, 4, 3, 20, 15};
int n = sizeof(arr) / sizeof(arr[0]);
// Your code here

Hint

Use int arr[] = {7, 10, 4, 3, 20, 15}; to create the array and int n = sizeof(arr) / sizeof(arr[0]); to get its size.

2

Set the kth position

Create an integer variable called k and set it to 3 to represent the kth smallest element to find.

DSA C

int arr[] = {7, 10, 4, 3, 20, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
// Your code here

Hint

Use int k = 3; to set the kth smallest element to find.

3

Build min heap and extract kth smallest

Implement the functions heapify and buildMinHeap to create a min heap from arr. Then, extract the minimum element k times to find the kth smallest element.

DSA C

int arr[] = {7, 10, 4, 3, 20, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;

// Your code here

Hint

Write heapify to maintain min heap property, buildMinHeap to build the heap, and extractMin to remove the smallest element. Then extract min k times.

4

Print the kth smallest element

Print the value of the variable kthSmallest which holds the kth smallest element.

DSA C

int arr[] = {7, 10, 4, 3, 20, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;

// heapify, buildMinHeap, extractMin functions here

buildMinHeap(arr, n);
int kthSmallest = -1;
int size = n;
for (int i = 0; i < k; i++) {
    kthSmallest = extractMin(arr, &size);
}

// Your code here

Hint

Use printf("%d\n", kthSmallest); to print the kth smallest element.

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