Kth Largest Element Using Max Heap in DSA C++

Mental Model

We use a max heap to keep track of the largest elements so we can quickly find the kth largest by removing the largest elements one by one.

Analogy: Imagine a pile of books stacked by height. The tallest book is on top. To find the kth tallest book, you remove the tallest books one by one until you reach the kth.

Max Heap Array Representation:
[ 9, 7, 8, 5, 6, 3, 4 ]
Heap Tree:
       9
     /   \
    7     8
   / \   / \
  5   6 3   4
↑ (root is largest)

Dry Run Walkthrough

Input: array: [3, 2, 1, 5, 6, 4], k = 2

Goal: Find the 2nd largest element in the array using a max heap

Step 1: Build max heap from array

[6, 5, 4, 2, 3, 1]

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

Step 2: Remove the largest element (6) from heap

[5, 3, 4, 2, 1]

Why: The root now is the 2nd largest element, which is our answer

Result:

[5, 3, 4, 2, 1]
Answer: 5

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int findKthLargest(vector<int>& nums, int k) {
    // Build max heap from nums
    make_heap(nums.begin(), nums.end());

    // Remove the largest element k-1 times
    for (int i = 0; i < k - 1; ++i) {
        pop_heap(nums.begin(), nums.end());
        nums.pop_back();
    }

    // The root of the heap is now the kth largest
    return nums.front();
}

int main() {
    vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;
    int result = findKthLargest(nums, k);
    cout << "Kth largest element is: " << result << endl;
    return 0;
}

make_heap(nums.begin(), nums.end());

Build max heap from the input array to organize elements by largest at root

pop_heap(nums.begin(), nums.end());

Move the largest element (root) to the end of the vector

nums.pop_back();

Remove the largest element from the heap to reduce heap size

return nums.front();

Return the root of the heap which is the kth largest element

Output

Kth largest element is: 5

Complexity Analysis

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

Space: O(1) because the heap is built in-place in the input array

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 (find largest element)

Returns the maximum element directly after building the heap

DSA C++

for (int i = 0; i < k - 1; ++i) { ... } handles zero iterations when k=1

k equals array size (find smallest element)

Removes all larger elements until the smallest remains at root

DSA C++

for loop runs k-1 times to pop all larger elements

array with duplicate elements

Duplicates are handled normally as heap stores all elements

DSA C++

make_heap and pop_heap work correctly with duplicates

When to Use This Pattern

When asked to find the kth largest or smallest element efficiently, think of using a heap to avoid full sorting.

Common Mistakes

Mistake: Not building the heap before popping elements
Fix: Always call make_heap before pop_heap to ensure heap property

Mistake: Removing elements fewer or more times than k-1
Fix: Remove exactly k-1 largest elements so the root is kth largest

Summary

Finds the kth largest element by building a max heap and removing the largest elements k-1 times.

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

The largest element is always at the root of a max heap, so popping k-1 times reveals the kth largest.