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 line of people sorted by height, but you only see the shortest person at the front. By asking the shortest person to step aside k times, the next shortest you see is the kth smallest.

Min Heap Array Representation:
[ 2, 5, 8, 10, 15 ]
Heap structure:
      2
     / \
    5   8
   / \
 10  15
↑ (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

Heap array: [3, 7, 4, 10, 20, 15]
Heap structure:
      3
     / \
    7   4
   / \   \
 10  20  15

Why: We need the smallest element at the root to extract easily

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

Heap array after removal: [4, 7, 15, 10, 20]
Heap structure:
      4
     / \
    7  15
   / \
 10  20

Why: Removing the smallest element moves us closer to the kth smallest

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

Heap array after removal: [7, 10, 15, 20]
Heap structure:
      7
     / \
   10  15
   / 
 20

Why: Second smallest removed, next extraction will be kth

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

Heap array after removal: [10, 20, 15]
Heap structure:
     10
    /  \
  20   15

Why: This is the kth smallest element

Result:

3rd smallest element is 7

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class MinHeap
{
    private List<int> heap = new List<int>();

    public MinHeap(int[] array)
    {
        foreach (var num in array)
            heap.Add(num);
        BuildHeap();
    }

    private void BuildHeap()
    {
        for (int i = Parent(heap.Count - 1); i >= 0; i--)
            HeapifyDown(i);
    }

    private int Parent(int i) => (i - 1) / 2;
    private int LeftChild(int i) => 2 * i + 1;
    private int RightChild(int i) => 2 * i + 2;

    private void HeapifyDown(int i)
    {
        int smallest = i;
        int left = LeftChild(i);
        int right = RightChild(i);

        if (left < heap.Count && heap[left] < heap[smallest])
            smallest = left;
        if (right < heap.Count && heap[right] < heap[smallest])
            smallest = right;

        if (smallest != i)
        {
            int temp = heap[i];
            heap[i] = heap[smallest];
            heap[smallest] = temp;
            HeapifyDown(smallest);
        }
    }

    public int ExtractMin()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("Heap is empty");

        int min = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);
        if (heap.Count > 0)
            HeapifyDown(0);
        return min;
    }
}

class Program
{
    static int KthSmallest(int[] arr, int k)
    {
        MinHeap minHeap = new MinHeap(arr);
        int result = -1;
        for (int i = 0; i < k; i++)
        {
            result = minHeap.ExtractMin();
        }
        return result;
    }

    static void Main()
    {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3;
        int kthSmallest = KthSmallest(arr, k);
        Console.WriteLine($"{k}th smallest element is {kthSmallest}");
    }
}

for (int i = Parent(heap.Count - 1); i >= 0; i--) HeapifyDown(i);

Build heap by heapifying from last parent to root

if (left < heap.Count && heap[left] < heap[smallest]) smallest = left; if (right < heap.Count && heap[right] < heap[smallest]) smallest = right;

Find smallest child to maintain min heap property

heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); HeapifyDown(0);

Replace root with last element, remove last, then heapify down to restore heap

for (int i = 0; i < k; i++) result = minHeap.ExtractMin();

Extract min k times to get kth smallest

Output

3th smallest element is 7

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each of the k extractions takes O(log n)

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

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

Edge Cases

k is larger than array length

Throws an exception or error because we try to extract more elements than exist

DSA C#

if (heap.Count == 0)
    throw new InvalidOperationException("Heap is empty");

array is empty

Throws an exception when trying to extract min from empty heap

DSA C#

if (heap.Count == 0)
    throw new InvalidOperationException("Heap is empty");

array has duplicates

Duplicates are handled normally; kth smallest counts duplicates as separate elements

DSA C#

No special guard needed; heap property handles duplicates

When to Use This Pattern

When you need the kth smallest or largest element efficiently, especially if k is small compared to n, use a heap to avoid full sorting.

Common Mistakes

Mistake: Extracting min fewer or more than k times
Fix: Ensure the loop runs exactly k times to get the kth smallest

Mistake: Not rebuilding heap properly after extraction
Fix: Call HeapifyDown after removing root to maintain heap property

Summary

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

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

The smallest element is always at the root of a min heap, so repeated extraction gives kth smallest.

Practice

1. What does a min heap guarantee about its root element when used to find the kth smallest element?

easy

A. The root is the average of all elements in the heap

B. The root is always the largest element in the heap

C. The root is the kth smallest element directly

D. The root is always the smallest element in the heap

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the root, so the root is the minimum of all elements in the heap.

2. Step 2: Relation to kth smallest element

   By removing the root k-1 times, the root then becomes the kth smallest element.

3. Final Answer:

   The root is always the smallest element in the heap -> Option D

4. Quick Check:

   Min heap root = smallest element [OK]

Hint: Min heap root is always smallest element [OK]

Common Mistakes:

• Thinking root is largest element
• Assuming root is directly kth smallest without removals
• Confusing min heap with max heap

2. Which of the following is the correct way to initialize a min heap in C# using PriorityQueue<int, int> to find the kth smallest element?

easy

A. var minHeap = new PriorityQueue();

B. var minHeap = new PriorityQueue<int>();

C. var minHeap = new PriorityQueue();

D. var minHeap = new PriorityQueue();

Solution

1. Step 1: Check PriorityQueue constructor syntax

   In C#, PriorityQueue<TElement, TPriority> requires two type parameters: element type and priority type. For integers, both are int.

2. Step 2: Validate options

   var minHeap = new PriorityQueue(); correctly uses PriorityQueue<int, int>. Options B, C, and D have incorrect or missing type parameters.

3. Final Answer:

   var minHeap = new PriorityQueue<int, int>(); -> Option C

4. Quick Check:

   Correct generic types for min heap = var minHeap = new PriorityQueue(); [OK]

Hint: Use PriorityQueue for min heap [OK]

Common Mistakes:

• Using only one generic type parameter
• Swapping element and priority types
• Using string instead of int for priority

3. What is the output of the following C# code snippet that uses a min heap to find the 3rd smallest element?

var nums = new int[] {7, 10, 4, 3, 20, 15};
var minHeap = new PriorityQueue();
foreach(var num in nums) {
    minHeap.Enqueue(num, num);
}
int kthSmallest = 0;
for(int i = 0; i < 3; i++) {
    kthSmallest = minHeap.Dequeue();
}
Console.WriteLine(kthSmallest);

medium

A. 7

B. 4

C. 10

D. 3

Solution

1. Step 1: Insert all elements into min heap

   Elements inserted: 7, 10, 4, 3, 20, 15. Min heap root is smallest element.

2. Step 2: Remove root 3 times to get 3rd smallest

   Dequeue order: 3 (1st), 4 (2nd), 7 (3rd). So, kthSmallest after 3 dequeues is 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   3rd smallest in array = 7 [OK]

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

Common Mistakes:

• Assuming kth smallest is the root without dequeues
• Confusing array order with heap order
• Off-by-one error in loop count

4. Identify the error in this code snippet that tries to find the 2nd smallest element using a min heap:

var nums = new int[] {5, 3, 8, 1};
var minHeap = new PriorityQueue();
foreach(var num in nums) {
    minHeap.Enqueue(num);
}
int secondSmallest = minHeap.Dequeue();
secondSmallest = minHeap.Dequeue();
Console.WriteLine(secondSmallest);

medium

A. Missing priority argument in Enqueue method

B. Using Dequeue twice is incorrect

C. Array initialization syntax is wrong

D. PriorityQueue cannot be used for integers

Solution

1. Step 1: Check Enqueue method usage

   The PriorityQueue<TElement, TPriority> requires two arguments for Enqueue: element and priority. Here only element is passed.

2. Step 2: Identify correct usage

   Correct call is minHeap.Enqueue(num, num); to use element as priority.

3. Final Answer:

   Missing priority argument in Enqueue method -> Option A

4. Quick Check:

   Enqueue needs element and priority [OK]

Hint: Enqueue needs element and priority both [OK]

Common Mistakes:

• Passing only one argument to Enqueue
• Confusing Dequeue count
• Wrong array syntax

5. Given a large array with possible duplicate values, which approach using a min heap is best to find the 4th smallest unique element efficiently?

hard

A. Insert all elements into min heap and dequeue 4 times

B. Insert unique elements into min heap, then dequeue 4 times

C. Sort the array and pick the 4th element directly

D. Use a max heap of size 4 to track smallest unique elements

Solution

1. Step 1: Understand duplicates impact

   Duplicates cause incorrect counting if all elements are inserted. We want unique elements only.

2. Step 2: Use a set to filter unique elements before min heap

   Insert only unique elements into min heap, then dequeue 4 times to get 4th smallest unique element.

3. Final Answer:

   Insert unique elements into min heap, then dequeue 4 times -> Option B

4. Quick Check:

   Filter duplicates before heap for unique kth smallest [OK]

Hint: Filter duplicates before heap to find unique kth smallest [OK]

Common Mistakes:

• Ignoring duplicates causing wrong kth element
• Using max heap incorrectly for this problem
• Sorting entire array when heap is more efficient