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.

Practice

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

easy

A. Use a hash map to count frequencies and find the kth largest

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

C. Sort the array and pick the kth element from the start

D. Build a min heap and extract the minimum element k times

Solution

1. Step 1: Understand max heap property

   A max heap always keeps the largest element at the root, so extracting the root gives the current largest element.

2. Step 2: Extract max k times

   By removing the root k times, the last extracted element is the kth largest.

3. Final Answer:

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

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
• Confusing kth largest with kth smallest

2. Which of the following is the correct C++ syntax to create a max heap from a vector nums in-place?

easy

A. std::priority_queue maxHeap(nums.begin(), nums.end());

B. std::make_heap(nums.begin(), nums.end(), std::greater<int>());

C. std::priority_queue<int> maxHeap(nums.begin(), nums.end());

D. std::make_heap(nums.begin(), nums.end());

Solution

1. Step 1: Understand std::make_heap default behavior

   By default, std::make_heap creates a max heap using operator<.

2. Step 2: Check syntax correctness

   std::make_heap(nums.begin(), nums.end()); correctly calls std::make_heap on the vector range without extra comparators, making a max heap in-place.

3. Final Answer:

   std::make_heap(nums.begin(), nums.end()); -> Option D

4. Quick Check:

   Default make_heap = max heap [OK]

Hint: Use std::make_heap without comparator for max heap [OK]

Common Mistakes:

• Using std::greater<int>() creates min heap
• Incorrect priority_queue constructor usage
• Confusing comparator direction

3. What is the output of the following C++ code snippet?

std::vector<int> nums = {3, 2, 1, 5, 6, 4};
std::make_heap(nums.begin(), nums.end());
for (int i = 0; i < 2; ++i) {
  std::pop_heap(nums.begin(), nums.end() - i);
}
int kthLargest = nums[0];
std::cout << kthLargest << std::endl;

medium

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Build max heap from nums

   Heap after make_heap is [6, 5, 4, 2, 3, 1] (largest at front).

2. Step 2: Perform two pop_heap operations

   First pop_heap moves 6 to end, second pop_heap moves 5 next to end. Now, nums[0] is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   After 2 pops, root = 5 [OK]

Hint: After popping max twice, root is 3rd largest [OK]

Common Mistakes:

• Assuming root stays 6 after pops
• Confusing pop_heap with pop_back
• Not adjusting heap size correctly

4. Identify the error in the following code to find the 3rd largest element using a max heap:

std::vector<int> nums = {7, 10, 4, 3, 20, 15};
std::priority_queue<int> maxHeap(nums.begin(), nums.end());
int kthLargest;
for (int i = 0; i < 3; ++i) {
  kthLargest = maxHeap.top();
  maxHeap.pop();
}
std::cout << kthLargest << std::endl;

medium

A. No error, code works correctly

B. Priority queue constructor syntax is incorrect

C. Loop should run k-1 times, not k

D. Must use std::make_heap instead of priority queue

Solution

1. Step 1: Check priority_queue construction

   Constructing maxHeap from vector range is valid and creates max heap.

2. Step 2: Verify loop logic for kth largest

   Loop extracts top element 3 times; last extracted is 3rd largest.

3. Final Answer:

   No error, code works correctly -> Option A

4. Quick Check:

   Priority queue pop k times = kth largest [OK]

Hint: Pop max k times from priority queue to get kth largest [OK]

Common Mistakes:

• Thinking priority_queue constructor is invalid
• Off-by-one error in loop count
• Confusing make_heap and priority_queue usage

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

hard

A. Use a min heap of size 5 to track unique elements while iterating

B. Sort the array and pick the 5th element from the end

C. Insert all elements into a set, then build a max heap from the set and pop 5 times

D. Build a max heap from the array and pop elements until 5 unique elements are found

Solution

1. Step 1: Efficiency priority

   For large n, O(n log k) is best vs O(n log n); min-heap size k scans once.

2. Step 2: Track unique top-k largest

   Iterate array, maintain min-heap of top 5 uniques (with set for lookup); add if new and > root or size <5, evict root otherwise.

3. Final Answer:

   Use a min heap of size 5 to track unique elements while iterating -> Option A

4. Quick Check:

   Min-heap size k + set = O(n log k) kth unique largest [OK]

Hint: Min heap size k + seen set for kth distinct largest O(n log k) [OK]

Common Mistakes:

• Full max heap pop until k unique (worst O(n log n) with dup leaders)
• Set first: O(n log n) time/space
• Sorting without explicit dedup logic