Kth Largest Element Using Max Heap in DSA C++ - Build from Scratch

Kth Largest Element Using Max Heap

📖 Scenario: You have a list of exam scores from students. You want to find the kth largest score to see who scored in the top group.

🎯 Goal: Build a program that uses a max heap to find the kth largest element from a list of numbers.

📋 What You'll Learn

Create a vector called scores with the exact values: 85, 92, 78, 90, 88, 76, 95

Create an integer variable called k and set it to 3

Use a max heap to find the kth largest score

Print the kth largest score using std::cout

💡 Why This Matters

🌍 Real World

Finding the kth largest value is useful in ranking systems, like finding the top scores in exams or competitions.

💼 Career

Understanding heaps and priority queues is important for software roles involving data processing, optimization, and real-time systems.

1

Create the scores vector

Create a std::vector<int> called scores with these exact values: 85, 92, 78, 90, 88, 76, 95

DSA C++

#include 
#include 

int main() {
    // Create the scores vector with given values
    // Your code here
}

Hint

Use std::vector<int> scores = {85, 92, 78, 90, 88, 76, 95}; to create the vector.

2

Set the value of k

Create an integer variable called k and set it to 3 inside main()

DSA C++

#include 
#include 

int main() {
    std::vector scores = {85, 92, 78, 90, 88, 76, 95};
    // Create variable k and set it to 3
    // Your code here
}

Hint

Write int k = 3; inside main().

3

Use a max heap to find the kth largest element

Use std::priority_queue<int> called maxHeap to store all elements from scores. Then pop from maxHeap exactly k - 1 times to remove the largest elements before the kth largest. Finally, store the top element of maxHeap in an integer variable called kthLargest

DSA C++

#include 
#include 
#include 

int main() {
    std::vector scores = {85, 92, 78, 90, 88, 76, 95};
    int k = 3;
    // Create maxHeap and push all scores
    // Pop k-1 times
    // Store top element in kthLargest
    // Your code here
}

Hint

Use std::priority_queue<int> maxHeap; and push all scores. Then pop k - 1 times. Finally, get the top element.

4

Print the kth largest score

Print the value of kthLargest using std::cout followed by a newline

DSA C++

#include 
#include 
#include 

int main() {
    std::vector scores = {85, 92, 78, 90, 88, 76, 95};
    int k = 3;
    std::priority_queue maxHeap;
    for (int score : scores) {
        maxHeap.push(score);
    }
    for (int i = 0; i < k - 1; i++) {
        maxHeap.pop();
    }
    int kthLargest = maxHeap.top();
    // Print kthLargest
    // Your code here
}

Hint

Use std::cout << kthLargest << std::endl; to print the result.

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