Kth Largest Element Using Max Heap in DSA C++ - Execution Trace

Concept Flow - Kth Largest Element Using Max Heap

Build Max Heap from array

↓

Extract max element (root)

↓

Replace root with last element

↓

Heapify to restore max heap

↓

Repeat extraction k times

↓

Last extracted element is kth largest

Build a max heap from the array, then extract the max element k times. The kth extracted max is the kth largest element.

Execution Sample

DSA C++

arr = [3, 2, 1, 5, 6, 4]; k = 2;
Build max heap;
Extract max k times;
Return kth extracted max;

Find the 2nd largest element by building a max heap and extracting max twice.

Execution Table

Step	Operation	Heap Array State	Pointer Changes	Visual State
1	Build max heap from [3,2,1,5,6,4]	[6,5,4,3,2,1]	heap built	Heap as tree: 6 / \ 5 4 / \ / 3 2 1
2	Extract max (1st extraction)	[1,5,4,3,2]	Extracted max=6; root replaced by 1	Heapify: 1 / \ 5 4 / \ 3 2
3	Heapify after extraction	[5,3,4,1,2]	Swapped 1 and 5	Heapify: 5 / \ 3 4 / \ 1 2
4	Extract max (2nd extraction)	[2,3,4,1]	Extracted max=5; root replaced by 2	Heapify: 2 / \ 3 4 / 1
5	Heapify after extraction	[4,3,2,1]	Swapped 2 and 4	Heapify: 4 / \ 3 2 / 1
6	Return kth largest element	5	kth extracted max	Result: 5

💡 After 2 extractions, the last extracted max (5) is the 2nd largest element.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
arr	[3,2,1,5,6,4]	[6,5,4,3,2,1]	[1,5,4,3,2]	[5,3,4,1,2]	[2,3,4,1]	[4,3,2,1]	[4,3,2,1]
extracted_max	N/A	N/A	6	N/A	5	N/A	5
heap_size	6	6	5	5	4	4	4

Key Moments - 3 Insights

Why do we replace the root with the last element after extracting max?

Because the root is removed, we need to fill the root position to keep the heap complete. The last element moves to root before heapify (see Step 2 and Step 4 in execution_table).

Why do we heapify after replacing the root?

Replacing root with last element may break max heap property. Heapify restores order by swapping down (see Step 3 and Step 5).

How do we know when to stop extracting?

We extract exactly k times. The kth extracted max is the kth largest element (see Step 6).

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the heap array state after extracting the max?

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

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

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

D [2,3,4,1]

💡 Hint

Check the 'Heap Array State' column at Step 2 in execution_table.

At which step does the heapify swap the root with a child to restore max heap?

A Step 3

B Step 6

C Step 1

D Step 2

💡 Hint

Look for 'Swapped 1 and 5' in Pointer Changes at Step 3.

If k was 1 instead of 2, what would be the kth largest element returned?

A 4

B 5

C 6

D 3

💡 Hint

The first extracted max is at Step 2 with value 6.

Concept Snapshot

Kth Largest Element Using Max Heap:
- Build max heap from array
- Extract max element k times
- Each extraction: remove root, replace with last element, heapify
- kth extracted max is kth largest
- Time: O(n + k log n)

Full Transcript

To find the kth largest element using a max heap, first build a max heap from the input array. The max heap ensures the largest element is at the root. Then, extract the max element k times. Each extraction removes the root, replaces it with the last element in the heap, and heapifies to restore the max heap property. After k extractions, the last extracted max is the kth largest element. This method efficiently finds the kth largest without sorting the entire array.

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