Kth Largest Element Using Max Heap in DSA C#

Mental Model

We use a special tree structure that always keeps the biggest number on top. By removing the biggest number k-1 times, the next biggest is the kth largest.

Analogy: Imagine a pile of books stacked so the thickest book is always on top. If you remove the thickest book repeatedly, the one you get after removing k-1 books is the kth thickest.

       [50]
      /     \
   [30]     [40]
   /  \     /  \
 [10] [20] [35] [25]

Dry Run Walkthrough

Input: array: [20, 10, 40, 30, 50, 25, 35], k=3

Goal: Find the 3rd largest element in the array using a max heap

Step 1: Build max heap from array

       [50]
      /     \
   [40]     [35]
   /  \     /  \
 [30] [10] [25] [20]

Why: We organize the array so the largest element is at the root for easy access

Step 2: Remove root (50), replace with last element (20), heapify

       [40]
      /     \
   [30]     [35]
   /  \     /  
 [20] [10] [25]

Why: Removing the largest element to find the next largest, then fix heap to keep max on top

Step 3: Remove root (40), replace with last element (25), heapify

       [35]
      /     \
   [30]     [25]
   /  \     
 [20] [10]

Why: Remove second largest and restore heap for next largest

Step 4: Remove root (35), this is the 3rd largest element

       [30]
      /     \
   [20]     [25]
   /  \     
       [10]

Why: The root now is the 3rd largest element after removing two bigger ones

Result:

35

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

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

    public MaxHeap(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 left = LeftChild(i);
        int right = RightChild(i);
        int largest = i;

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

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

    public int ExtractMax()
    {
        if (heap.Count == 0) throw new InvalidOperationException("Heap is empty");
        int max = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);
        if (heap.Count > 0) HeapifyDown(0);
        return max;
    }

    public int Count() => heap.Count;
}

class Program
{
    static void Main()
    {
        int[] array = {20, 10, 40, 30, 50, 25, 35};
        int k = 3;
        MaxHeap maxHeap = new MaxHeap(array);

        int kthLargest = 0;
        for (int i = 0; i < k; i++)
        {
            kthLargest = maxHeap.ExtractMax();
        }

        Console.WriteLine(kthLargest);
    }
}

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

build max heap by heapifying from bottom up

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

extract max by removing root and restoring heap property

for (int i = 0; i < k; i++) kthLargest = maxHeap.ExtractMax();

remove max k times to get kth largest

Output

35

Complexity Analysis

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

Space: O(n) because we store all elements in the heap list

vs Alternative: Compared to sorting the array O(n log n), this approach is faster when k is small because heap build is O(n) and extractions are O(k log n)

Edge Cases

k is larger than array length

Throws 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 exception when trying to build or extract from empty heap

DSA C#

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

array has duplicate elements

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

DSA C#

No special guard needed; heap handles duplicates naturally

When to Use This Pattern

When asked to find the kth largest or smallest element efficiently, think of using a heap to quickly access and remove the largest or smallest elements without full sorting.

Common Mistakes

Mistake: Not rebuilding the heap after removing the root element
Fix: Call HeapifyDown after replacing root with last element to restore heap property

Mistake: Extracting max fewer or more than k times
Fix: Ensure exactly k extractions to get the kth largest element

Summary

Finds the kth largest element by building a max heap and extracting the max k times.

Use when you want the kth largest element without sorting the entire array.

The largest element is always at the root, so removing it k-1 times reveals the kth largest.

Practice

1. What is the main idea behind finding the kth largest element using a max heap?

easy

A. Build a max heap from the array and extract the maximum element k times

B. Sort the array and pick the element at index k

C. Use a min heap to store all elements and extract the minimum k times

D. Traverse the array and count elements greater than k

Solution

1. Step 1: Build a max heap from the array

   A max heap is a binary tree where the parent node is always greater than its children. Building it from the array organizes elements so the largest is at the root.

2. Step 2: Extract the maximum element k times

   Extracting the root removes the largest element. Doing this k times leaves the kth largest element at the root after the last extraction.

3. Final Answer:

   Build max heap and extract max k times -> Option A

4. Quick Check:

   Max heap extraction = kth largest element [OK]

Hint: Extract max from max heap k times to get kth largest [OK]

Common Mistakes:

• Using min heap instead of max heap
• Sorting and picking wrong index
• Counting elements incorrectly

2. Which of the following is the correct C# syntax to create a max heap using PriorityQueue<int, int> where the largest element has the highest priority?

easy

A. var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => a - b));

B. var maxHeap = new PriorityQueue();

C. var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => b - a));

D. var maxHeap = new PriorityQueue(Comparer<int>.Default);

Solution

1. Step 1: Understand PriorityQueue default behavior

   By default, PriorityQueue<TElement, TPriority> in C# is a min heap based on priority, so smaller priority values come out first.

2. Step 2: Use custom comparer to reverse order for max heap

   To make it a max heap, we provide a comparer that reverses the order: b - a instead of a - b. This makes larger priorities come out first.

3. Final Answer:

   var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a)); -> Option C

4. Quick Check:

   Custom comparer reverses order for max heap [OK]

Hint: Use comparer (b - a) for max heap in PriorityQueue [OK]

Common Mistakes:

• Using default comparer which creates min heap
• Swapping comparer parameters incorrectly
• Not providing any comparer

3. What will be the output of the following C# code snippet that finds the 3rd largest element using a max heap?

int[] nums = {4, 1, 7, 3, 8, 5};
var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => b - a));
foreach (var num in nums) maxHeap.Enqueue(num, num);
int kthLargest = 0;
for (int i = 0; i < 3; i++) kthLargest = maxHeap.Dequeue();
Console.WriteLine(kthLargest);

medium

A. 7

B. 5

C. 4

D. 3

Solution

1. Step 1: Build max heap from array

   The max heap will organize elements so the largest is at the root: 8, 7, 5, 4, 3, 1.

2. Step 2: Extract max 3 times

   First dequeue: 8 (largest)
   Second dequeue: 7 (second largest)
   Third dequeue: 5 (third largest)

3. Final Answer:

   5 -> Option B

4. Quick Check:

   3rd largest element = 5 [OK]

Hint: Extract max 3 times; last extracted is 3rd largest [OK]

Common Mistakes:

• Confusing index with value
• Extracting fewer or more times
• Using min heap instead of max heap

4. The following code attempts to find the 2nd largest element using a max heap but throws an exception. What is the error?

int[] nums = {10, 20};
var maxHeap = new PriorityQueue();
foreach (var num in nums) maxHeap.Enqueue(num, num);
int kthLargest = 0;
for (int i = 0; i <= 2; i++) kthLargest = maxHeap.Dequeue();
Console.WriteLine(kthLargest);

medium

A. The loop runs one time too many causing an exception

B. PriorityQueue is not initialized with a comparer for max heap

C. The array has fewer elements than k

D. Enqueue method is used incorrectly

Solution

1. Step 1: Check loop bounds for dequeue

   The loop runs from 0 to 2 inclusive, which means 3 iterations. But the array has only 2 elements.

2. Step 2: Understand dequeue behavior

   After 2 dequeues, the heap is empty. The 3rd dequeue causes an InvalidOperationException because the heap is empty.

3. Final Answer:

   The loop runs one time too many causing an exception -> Option A

4. Quick Check:

   Loop runs 3 times but only 2 elements exist [OK]

Hint: Loop should run k times, not k+1 times [OK]

Common Mistakes:

• Using <= instead of < in loop
• Not checking array size before dequeue
• Ignoring exception from empty heap

5. Given a large array with many duplicate elements, which approach using a max heap is best to find the 4th largest unique element efficiently?

hard

A. Build a max heap from all elements and extract max 4 times

B. Use a min heap of size 4 to track largest unique elements

C. Sort the array and pick the 4th element from the end

D. Use a max heap but skip duplicates during extraction until 4 unique elements are found

Solution

1. Step 1: Understand duplicates affect kth largest unique element

   Simply extracting max 4 times may count duplicates multiple times, giving wrong result.

2. Step 2: Skip duplicates during extraction

   Extract max repeatedly, but ignore elements equal to previously extracted ones until 4 unique elements are found.

3. Step 3: Why other options are less efficient

   Sorting is O(n log n) and may be costly for large arrays. Using a min heap of size 4 does not handle duplicates well without extra checks.

4. Final Answer:

   Use a max heap but skip duplicates during extraction until 4 unique elements are found -> Option D

5. Quick Check:

   Skip duplicates while extracting max for unique kth largest [OK]

Hint: Skip duplicates while extracting max to find unique kth largest [OK]

Common Mistakes:

• Counting duplicates as separate largest elements
• Using min heap without uniqueness checks
• Sorting entire array unnecessarily