Kth Largest Element Using Max Heap in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Largest Element Extraction

What is the output of the following C++ code that finds the 3rd largest element using a max heap?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

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

int main() {
    std::vector<int> nums = {7, 10, 4, 3, 20, 15};
    int k = 3;
    std::cout << findKthLargest(nums, k) << std::endl;
    return 0;
}

A 20

B 10

C 15

D 7

💡 Hint

Remember that the max heap pops the largest element first.

The max heap will pop elements in descending order: 20, 15, then 10. The 3rd largest element is 10.

🧠 Conceptual

intermediate

Understanding Max Heap Behavior

If you insert the numbers [5, 3, 8, 4, 1] into a max heap, what will be the root element after all insertions?

A 8

B 3

C 4

D 5

💡 Hint

The root of a max heap is always the largest element.

A max heap always keeps the largest element at the root. Among the numbers, 8 is the largest.

🔧 Debug

advanced

Identify the Error in Kth Largest Element Code

What error will this C++ code produce when trying to find the 2nd largest element using a max heap?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

int findKthLargest(std::vector<int>& nums, int k) {
    std::priority_queue<int> maxHeap;
    for (int num : nums) {
        maxHeap.push(num);
    }
    int result = 0;
    for (int i = 0; i <= k; ++i) {
        result = maxHeap.top();
        maxHeap.pop();
    }
    return result;
}

int main() {
    std::vector<int> nums = {6, 5};
    int k = 2;
    std::cout << findKthLargest(nums, k) << std::endl;
    return 0;
}

A Outputs 6

B Outputs 5

C Compilation error

D Runtime error: popping from empty heap

💡 Hint

Check the loop condition carefully.

The loop runs k+1 times instead of k times, causing an extra pop that empties the heap and then tries to pop again, causing runtime error.

🚀 Application

advanced

Number of Elements in Max Heap After Partial Extraction

Given a max heap built from 8 elements, after extracting the top 4 largest elements, how many elements remain in the heap?

A 4

B 3

C 5

D 0

💡 Hint

Each extraction removes one element from the heap.

Starting with 8 elements, extracting 4 removes 4 elements, leaving 4 elements in the heap.

❓ Predict Output

expert

Output of Kth Largest Element with Duplicate Values

What is the output of this C++ code that finds the 4th largest element using a max heap when the input vector contains duplicates?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

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

int main() {
    std::vector<int> nums = {4, 2, 4, 5, 6, 5, 1};
    int k = 4;
    std::cout << findKthLargest(nums, k) << std::endl;
    return 0;
}

A 2

B 5

C 4

D 6

💡 Hint

Duplicates are treated as separate elements in the heap.

The max heap pops elements in order: 6, 5, 5, then 4. The 4th largest element is 4.