Kth Largest Element Using Max Heap in DSA C

Mental Model

We use a max heap to always get the largest element quickly, then remove the largest elements until we reach the kth largest.

Analogy: Imagine a pile of boxes stacked by size. You keep taking the biggest box off the top until you reach the kth box you took.

Max Heap Array Representation:
       [50]
      /    \
   [30]    [40]
   /  \    /  \
 [10] [20][35] [25]

Array form: [50, 30, 40, 10, 20, 35, 25]

Dry Run Walkthrough

Input: array: [20, 10, 40, 30, 50, 25, 35], k=3

Goal: Find the 3rd largest element in the array using a max heap

Step 1: Build max heap from array

[50, 30, 40, 10, 20, 35, 25]

Why: We need a max heap so the largest element is always at the root

Step 2: Extract max (50), heapify to restore max heap

[40, 30, 35, 10, 20, 25]

Why: Remove largest element, then fix heap to get next largest at root

Step 3: Extract max (40), heapify to restore max heap

[35, 30, 25, 10, 20]

Why: Remove second largest, fix heap for next largest

Step 4: Extract max (35), this is the 3rd largest element

[30, 20, 25, 10]

Why: The 3rd extraction gives the 3rd largest element

Result:

3rd largest element is 35

Annotated Code

DSA C

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void maxHeapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // left child index
    int right = 2 * i + 2; // right child index

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        swap(&arr[i], &arr[largest]); // swap root with largest child
        maxHeapify(arr, n, largest); // recursively heapify affected subtree
    }
}

void buildMaxHeap(int arr[], int n) {
    // Build max heap from bottom up
    for (int i = n / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, n, i); // heapify each non-leaf node
    }
}

int extractMax(int arr[], int *n) {
    if (*n <= 0) return -1; // empty heap
    int max = arr[0]; // root is max
    arr[0] = arr[*n - 1]; // move last element to root
    (*n)--; // reduce heap size
    maxHeapify(arr, *n, 0); // restore max heap
    return max;
}

int kthLargest(int arr[], int n, int k) {
    buildMaxHeap(arr, n); // step 1: build max heap
    int size = n;
    int maxVal = -1;
    for (int i = 0; i < k; i++) {
        maxVal = extractMax(arr, &size); // extract max k times
    }
    return maxVal; // kth largest
}

int main() {
    int arr[] = {20, 10, 40, 30, 50, 25, 35};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int result = kthLargest(arr, n, k);
    printf("%d\n", result);
    return 0;
}

buildMaxHeap(arr, n);

build max heap so largest element is at root

maxVal = extractMax(arr, &size);

extract max element and reduce heap size

maxHeapify(arr, *n, 0);

restore max heap property after extraction

Output

35

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each extraction takes O(log n) repeated k times

Space: O(1) because we modify the array in place without extra space

vs Alternative: Naive approach sorts the entire array in O(n log n), this approach is faster when k is small compared to n

Edge Cases

k is larger than array size

extractMax returns -1 indicating no kth largest element

DSA C

if (*n <= 0) return -1;

array is empty

extractMax returns -1 immediately

DSA C

if (*n <= 0) return -1;

k is 1 (largest element)

returns the maximum element correctly

DSA C

for (int i = 0; i < k; i++) { maxVal = extractMax(arr, &size); }

When to Use This Pattern

When you need the kth largest element quickly without sorting the whole array, use a max heap to extract the largest elements step by step.

Common Mistakes

Mistake: Not rebuilding or heapifying after extracting the max element
Fix: Call maxHeapify after moving last element to root to restore heap property

Summary

Finds the kth largest element by building a max heap and extracting the max k times.

Use when you want kth largest without fully sorting the array.

The largest element is always at the root of the max heap, so extracting max repeatedly gives kth largest.

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