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.