Kth Largest Element Using Max Heap in DSA C++ - Time & Space Complexity

Time Complexity: Kth Largest Element Using Max Heap

O(n + k log n)

Understanding Time Complexity

We want to understand how long it takes to find the kth largest number using a max heap.

How does the time needed grow as the list of numbers gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <vector>
#include <queue>

int findKthLargest(std::vector<int>& nums, int k) {
    std::priority_queue<int> maxHeap(nums.begin(), nums.end());
    for (int i = 1; i < k; ++i) {
        maxHeap.pop();
    }
    return maxHeap.top();
}
    

This code builds a max heap from the list and removes the largest element k-1 times to get the kth largest.

Identify Repeating Operations

• Primary operation: Building the max heap and popping elements from it.
• How many times: Building heap once over n elements, then popping k-1 times.

How Execution Grows With Input

Building the heap takes time proportional to the number of elements, and each pop takes time related to the heap size.

Input Size (n)	Approx. Operations
10	Build heap ~20 ops, pop up to k times ~k*log 10
100	Build heap ~700 ops, pop up to k times ~k*log 100
1000	Build heap ~10,000 ops, pop up to k times ~k*log 1000

Pattern observation: Building the heap grows roughly linearly with n, popping grows with k times log n.

Final Time Complexity

Time Complexity: O(n + k log n)

This means the time grows mostly with the size of the list and the number of pops, each pop taking a bit longer as the list grows.

Common Mistake

[X] Wrong: "Popping k times from the heap is O(k) because each pop is just one step."

[OK] Correct: Each pop requires rearranging the heap, which takes time proportional to log n, not constant time.

Interview Connect

Understanding this time complexity helps you explain how efficient your solution is and why heaps are useful for selection problems.

Self-Check

"What if we used a min heap of size k instead of a max heap of size n? How would the time complexity change?"