Kth Smallest Element Using Min Heap in DSA C++

Mental Model

A min heap always keeps the smallest element at the top, so by removing the smallest element k times, we get the kth smallest.

Analogy: Imagine a pile of numbered balls where the smallest ball is always on top. Taking the top ball k times gives you the kth smallest ball.

Min Heap Array Representation:
[ 2, 3, 5, 7, 8, 10 ]
Heap structure:
      2
     / \
    3   5
   / \  /
  7  8 10
↑ (root is smallest)

Dry Run Walkthrough

Input: array: [7, 10, 4, 3, 20, 15], k=3

Goal: Find the 3rd smallest element in the array using a min heap

Step 1: Build min heap from array

[3, 7, 4, 10, 20, 15]

Why: Heapify rearranges array so smallest element is at root

Step 2: Extract min (1st smallest): remove 3

[4, 7, 15, 10, 20]

Why: Remove smallest element and re-heapify to maintain min heap

Step 3: Extract min (2nd smallest): remove 4

[7, 10, 15, 20]

Why: Remove next smallest and re-heapify

Step 4: Extract min (3rd smallest): remove 7

[10, 20, 15]

Why: Remove kth smallest element; this is the answer

Result:

Heap after 3 extractions: [10, 20, 15]
3rd smallest element: 7

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int kthSmallest(vector<int>& nums, int k) {
    // Create a min heap from nums
    priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.end());

    int kth_min = -1;
    // Extract min k times
    for (int i = 0; i < k; i++) {
        kth_min = minHeap.top(); // get smallest
        minHeap.pop();          // remove smallest
    }
    return kth_min;
}

int main() {
    vector<int> nums = {7, 10, 4, 3, 20, 15};
    int k = 3;
    int result = kthSmallest(nums, k);
    cout << result << endl;
    return 0;
}

priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.end());

Build min heap from input array

kth_min = minHeap.top();

Get current smallest element from heap

minHeap.pop();

Remove smallest element to move to next smallest

Output

7

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and extracting k times takes O(k log n)

Space: O(n) because the heap stores all n elements

vs Alternative: Sorting the array takes O(n log n), which is slower than heap approach when k is small

Edge Cases

k is 1 (smallest element)

Returns the minimum element correctly

DSA C++

for (int i = 0; i < k; i++) {

k equals array size

Returns the maximum element correctly

DSA C++

for (int i = 0; i < k; i++) {

k is larger than array size

Undefined behavior, code assumes valid k; no guard in code

When to Use This Pattern

When you need the kth smallest or largest element efficiently, use a heap to avoid full sorting.

Common Mistakes

Mistake: Using a max heap instead of a min heap for kth smallest
Fix: Use a min heap (priority_queue with greater comparator) to get smallest elements first

Mistake: Not popping from the heap k times
Fix: Pop exactly k times to reach the kth smallest element

Summary

Finds the kth smallest element by building a min heap and extracting the smallest k times.

Use when you want kth smallest without sorting the entire array.

The smallest element is always at the top of a min heap, so popping k times reveals the kth smallest.

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