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

Kth Smallest Element Using Min Heap

📖 Scenario: You have a list of numbers representing the scores of players in a game. You want to find the kth smallest score to understand the performance threshold.

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

📋 What You'll Learn

Create a vector called scores with the exact values: 12, 3, 5, 7, 19

Create an integer variable called k and set it to 3

Use a priority_queue with greater<int> to create a min heap from scores

Extract the smallest elements from the min heap until you reach the kth smallest

Print the kth smallest element

💡 Why This Matters

🌍 Real World

Finding the kth smallest element is useful in ranking systems, like finding the third fastest runner or the 5th lowest price in a list.

💼 Career

Understanding heaps and priority queues is important for software engineers working on algorithms, data processing, and performance optimization.

1

Create the scores vector

Create a std::vector<int> called scores with these exact values: 12, 3, 5, 7, 19

DSA C++

#include 
#include 

int main() {
    // Create the scores vector with values 12, 3, 5, 7, 19
    // Your code here
    return 0;
}

Hint

Use std::vector<int> scores = {12, 3, 5, 7, 19}; to create the vector.

2

Set the value of k

Create an integer variable called k and set it to 3

DSA C++

#include 
#include 

int main() {
    std::vector scores = {12, 3, 5, 7, 19};
    // Create an integer variable k and set it to 3
    // Your code here
    return 0;
}

Hint

Write int k = 3; to create the variable.

3

Create a min heap and extract kth smallest

Include <queue> and <functional>. Create a std::priority_queue<int, std::vector<int>, std::greater<int>> called minHeap using scores. Then, pop elements from minHeap exactly k - 1 times.

DSA C++

#include 
#include 
#include 
#include 

int main() {
    std::vector scores = {12, 3, 5, 7, 19};
    int k = 3;
    // Create a min heap called minHeap from scores
    // Pop k-1 elements from minHeap
    // Your code here
    return 0;
}

Hint

Use std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap(scores.begin(), scores.end()); to create the min heap.

Use a for loop to pop k - 1 elements.

4

Print the kth smallest element

Print the top element of minHeap which is the kth smallest element.

DSA C++

#include 
#include 
#include 
#include 

int main() {
    std::vector scores = {12, 3, 5, 7, 19};
    int k = 3;

    std::priority_queue, std::greater> minHeap(scores.begin(), scores.end());

    for (int i = 0; i < k - 1; i++) {
        minHeap.pop();
    }

    // Print the kth smallest element
    // Your code here
    return 0;
}

Hint

Use std::cout << minHeap.top() << std::endl; 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 min heap from the array and extract the minimum element k times

C. Build a max heap and extract the maximum 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.

3. Final Answer:

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

4. Quick Check:

   Min heap 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
• Confusing kth smallest with kth largest

2. Which of the following C++ STL functions is used to create a min heap from a vector?

easy

A. std::make_heap(v.begin(), v.end(), std::greater<int>())

B. std::push_heap(v.begin(), v.end())

C. std::make_heap(v.begin(), v.end())

D. std::pop_heap(v.begin(), v.end())

Solution

1. Step 1: Understand default heap behavior

   By default, std::make_heap creates a max heap.

2. Step 2: Use comparator for min heap

   Passing std::greater<int>() as comparator creates a min heap.

3. Final Answer:

   std::make_heap with std::greater comparator -> Option A

4. Quick Check:

   std::make_heap + std::greater = min heap [OK]

Hint: Use std::greater<int>() with make_heap for min heap [OK]

Common Mistakes:

• Using default make_heap creates max heap
• Confusing push_heap and make_heap
• Using pop_heap to create heap

3. What will be the output of the following code snippet?

std::vector<int> v = {7, 10, 4, 3, 20, 15};
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap(v.begin(), v.end());
int k = 3;
int kthSmallest;
for (int i = 0; i < k; i++) {
    kthSmallest = minHeap.top();
    minHeap.pop();
}
std::cout << kthSmallest << std::endl;

medium

A. 10

B. 4

C. 7

D. 3

Solution

1. Step 1: Build min heap from vector

   The min heap elements in order of extraction are 3, 4, 7, 10, 15, 20.

2. Step 2: Extract min 3 times

   Extracted elements: 3 (1st), 4 (2nd), 7 (3rd). So, kth smallest (k=3) is 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   3rd smallest element = 7 [OK]

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

Common Mistakes:

• Confusing kth smallest with kth largest
• Off-by-one error in loop
• Not popping from heap after top

4. Identify the error in the following code to find the kth smallest element using a min heap:

std::vector<int> nums = {5, 3, 8, 4, 2};
std::priority_queue<int> minHeap(nums.begin(), nums.end());
int k = 2;
int result;
for (int i = 0; i < k; i++) {
    result = minHeap.top();
    minHeap.pop();
}
std::cout << result << std::endl;

medium

A. priority_queue creates max heap by default, not min heap

B. Loop should run k+1 times

C. pop() should be called before top()

D. Vector initialization syntax is incorrect

Solution

1. Step 1: Check priority_queue default behavior

   By default, std::priority_queue is a max heap, so it will give the largest element first.

2. Step 2: Effect on kth smallest extraction

   Extracting top k times from max heap gives kth largest, not kth smallest.

3. Final Answer:

   priority_queue creates max heap by default, not min heap -> Option A

4. Quick Check:

   Default priority_queue = max heap [OK]

Hint: Use comparator for min heap; default is max heap [OK]

Common Mistakes:

• Assuming priority_queue is min heap by default
• Wrong loop count for kth element
• Calling pop before top

5. Given a large unsorted array with possible duplicate elements, which approach using a min heap is most efficient to find the kth smallest unique element?

hard

A. Build a min heap of all elements and extract unique elements until kth unique is found

B. Sort the array and iterate to find kth unique element

C. Use a max heap of size k to track kth smallest unique element while iterating

D. Use a hash set to remove duplicates, then build min heap and extract kth element

Solution

1. Step 1: Remove duplicates using hash set

   Using a hash set removes duplicates efficiently, reducing the data size.

2. Step 2: Build min heap from unique elements and extract kth

   Building min heap from unique elements and extracting kth smallest is efficient and correct.

3. Final Answer:

   Use a hash set to remove duplicates, then build min heap and extract kth element -> Option D

4. Quick Check:

   Remove duplicates first, then min heap extraction [OK]

Hint: Remove duplicates first, then use min heap for kth smallest [OK]

Common Mistakes:

• Extracting kth smallest without removing duplicates
• Using max heap instead of min heap
• Sorting entire array unnecessarily