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

int findKthLargest(int arr[], int n, int k) {
  buildMaxHeap(arr, n);
  int kth;
  for (int i = 0; i < k; i++) {
    kth = arr[0];
    swap(arr[0], arr[n - 1 - i]);
    heapify(arr, 0, n - 1 - i);
  }
  return kth;
}

Build max heap, then extract max k times: save root before swap, swap root with last element and heapify. The kth (last) extracted is kth largest.

Execution Table

Step	Operation	Heap Array State	Pointer Changes	Visual State
1	Build max heap from array [3,2,1,5,6,4]	[6,5,4,3,2,1]	heap size = 6	Max heap formed: 6 at root, children 5 and 4, heap property holds
2	Extract max (1st extraction): swap root and last element	[1,5,4,3,2,6]	heap size = 5	6 removed, heap size reduced, root replaced with 1
3	Heapify root to restore max heap	[5,3,4,1,2,6]	heap size = 5	Heap restored: 5 at root, children 3 and 4
4	Extract max (2nd extraction): swap root and last element	[2,3,4,1,5,6]	heap size = 4	5 removed, heap size reduced, root replaced with 2
5	Heapify root to restore max heap	[4,3,2,1,5,6]	heap size = 4	Heap restored: 4 at root, children 3 and 2
6	Extract max (3rd extraction): swap root and last element	[1,3,2,4,5,6]	heap size = 3	4 removed, heap size reduced, root replaced with 1
7	Heapify root to restore max heap	[3,1,2,4,5,6]	heap size = 3	Heap restored: 3 at root, children 1 and 2
8	k=3 extractions done, kth largest element is last extracted	[3,1,2,4,5,6]	heap size = 3	4 is the 3rd largest element

💡 After k extractions, kth extracted element is kth largest

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	Final
heap array	[3,2,1,5,6,4]	[6,5,4,3,2,1]	[5,3,4,1,2,6]	[4,3,2,1,5,6]	[3,1,2,4,5,6]	[3,1,2,4,5,6]
heap size	6	6	5	4	3	3
extracted elements	[]	[]	[6]	[6,5]	[6,5,4]	[6,5,4]
root element	3	6	5	4	3	3

Key Moments - 3 Insights

Why do we swap the root with the last element before heapifying?

Swapping moves the max element (root) to the end to exclude it from the heap, then heapify restores max heap on the reduced heap (see steps 2 and 4 in execution_table).

Why does heap size reduce after each extraction?

Because each extraction removes the largest element from the heap, so heap size decreases to exclude extracted elements (tracked in variable_tracker).

Why is the kth extracted element the kth largest?

Because each extraction removes the current largest remaining element, so they come out in descending order; the kth one is kth largest (see step 8 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the root element after heapify?

A 5

B 1

C 6

D 4

💡 Hint

Check the 'Heap Array State' column at step 3 in execution_table

At which step does the heap size reduce to 4?

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Pointer Changes' column for heap size changes in execution_table

If k was 2 instead of 3, what would be the kth largest element after extraction?

A 6

B 5

C 4

D 3

💡 Hint

Refer to the root element after the first extraction in variable_tracker and execution_table

Concept Snapshot

Kth Largest Element Using Max Heap:
- Build max heap from array
- Extract max element k times:
  save root, swap root with last, reduce heap size, heapify
- kth (last) extracted is kth largest
- Time complexity: O(n + k log n)
- Useful for finding kth largest efficiently

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 by saving the root, swapping the root with the last element in the heap, reducing the heap size, and heapifying the root to restore the max heap property. The kth (last) extracted element 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. Build a min heap and extract the minimum element k times

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. Use a hash map to count frequencies and find the kth largest

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 to get kth largest

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

3. Final Answer:

   Build a 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 find kth largest [OK]

Common Mistakes:

• Using min heap instead of max heap
• Extracting fewer or more than k times
• Sorting and picking wrong index

2. Which of the following is the correct C code snippet to build a max heap from an array arr of size n?

easy

A. for (int i = n - 1; i >= 0; i--) heapify(arr, n, i);

B. for (int i = 0; i < n; i++) heapify(arr, n, i);

C. for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

D. for (int i = 1; i < n; i++) heapify(arr, n, i);

Solution

1. Step 1: Identify heapify starting point

   Heapify must start from the last non-leaf node, which is at index n/2 - 1, moving upwards.

2. Step 2: Loop from n/2 - 1 down to 0

   This ensures all subtrees satisfy max heap property, building the heap correctly.

3. Final Answer:

   for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); -> Option C

4. Quick Check:

   Build max heap loop = from n/2 - 1 down [OK]

Hint: Build heap from last non-leaf node down to root [OK]

Common Mistakes:

• Starting heapify from 0 upwards
• Starting heapify from last element
• Using wrong loop boundaries

3. What is the output of the following C code snippet to find the 3rd largest element?

int arr[] = {4, 10, 3, 5, 1};
int n = 5;
int k = 3;
buildMaxHeap(arr, n);
int result;
for (int i = 0; i < k; i++) {
    result = extractMax(arr, &n);
}
printf("%d\n", result);

Assume buildMaxHeap and extractMax work correctly.

medium

A. 3

B. 5

C. 10

D. 4

Solution

1. Step 1: Build max heap from array

   Max heap root is 10, heap structure after build: [10, 5, 3, 4, 1]

2. Step 2: Extract max 3 times

   1st extract: 10, 2nd extract: 5, 3rd extract: 4 (this is the 3rd largest)

3. Final Answer:

   4 -> Option D

4. Quick Check:

   3rd largest element = 4 [OK]

Hint: Extract max k times; last extracted is kth largest [OK]

Common Mistakes:

• Confusing 3rd largest with 3rd smallest
• Not updating heap size after extraction
• Assuming array is sorted after buildMaxHeap

4. Identify the bug in the following code snippet that tries to find the 2nd largest element using a max heap:

int arr[] = {7, 2, 9, 4};
int n = 4;
int k = 2;
buildMaxHeap(arr, n);
int result = extractMax(arr, n);
for (int i = 1; i < k; i++) {
    result = extractMax(arr, n);
}
printf("%d\n", result);

medium

A. The heap size n is not updated after extraction

B. The loop should start from i = 0 instead of 1

C. The array is not sorted before building the heap

D. The variable result is not initialized

Solution

1. Step 1: Check heap size update after extraction

   Extracting max reduces heap size, but n is passed unchanged, so heap operations are incorrect.

2. Step 2: Correct by passing pointer or updating n

   Heap size must decrease after each extraction to maintain heap property correctly.

3. Final Answer:

   Heap size n is not updated after extraction -> Option A

4. Quick Check:

   Update heap size after extractMax [OK]

Hint: Always update heap size after extraction [OK]

Common Mistakes:

• Not decreasing heap size after extractMax
• Incorrect loop start index
• Assuming array must be sorted before heap

5. Given an array arr = {12, 3, 5, 7, 19, 0, 4}, write the steps to find the 4th largest element using a max heap. What is the 4th largest element?

hard

A. 5

B. 3

C. 4

D. 7

Solution

1. Step 1: Build max heap from the array

   Heap root is 19, heap structure after build: [19, 12, 5, 7, 3, 0, 4]

2. Step 2: Extract max 4 times

   1st extract: 19, 2nd extract: 12, 3rd extract: 7, 4th extract: 5

3. Step 3: Identify the 4th largest element

   The 4th extracted max is 5 (since extraction order is 19, 12, 7, 5, the 4th largest is 5)

4. Final Answer:

   5 -> Option A

5. Quick Check:

   4th largest element = 5 [OK]

Hint: Extract max k times; last extracted is kth largest [OK]

Common Mistakes:

• Mixing extraction order and element values
• Counting extraction incorrectly
• Not building max heap properly