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.