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

Kth Largest Element Using Max Heap

📖 Scenario: You have a list of numbers representing scores in a game. You want to find the kth largest score to award a prize.

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

📋 What You'll Learn

Create an array called numbers with exactly these values: 20, 15, 30, 5, 10, 25, 35

Create an integer variable called k and set it to 3

Build a max heap from the numbers array

Extract the maximum element from the heap k times to find the kth largest element

Print the kth largest element

💡 Why This Matters

🌍 Real World

Finding the kth largest value is useful in games for ranking scores, in finance for top transactions, or in data analysis for thresholding.

💼 Career

Understanding heaps and selection algorithms is important for software engineers working on performance-critical applications, databases, and real-time systems.

1

Create the initial array of numbers

Create an integer array called numbers with these exact values: 20, 15, 30, 5, 10, 25, 35

DSA C

# Create the array numbers with the given values
# Your code here

Hint

Use int numbers[] = {20, 15, 30, 5, 10, 25, 35}; to create the array.

2

Set the value of k

Create an integer variable called k and set it to 3

DSA C

int numbers[] = {20, 15, 30, 5, 10, 25, 35};
# Create the variable k and set it to 3
# Your code here

Hint

Use int k = 3; to create the variable.

3

Build max heap and find kth largest element

Write functions to build a max heap from the numbers array and extract the maximum element. Then, extract the maximum element k times to find the kth largest element. Store the kth largest element in an integer variable called kth_largest.

DSA C

int numbers[] = {20, 15, 30, 5, 10, 25, 35};
int k = 3;
// Write max heap functions and find kth largest element
// Your code here

Hint

Use build_max_heap to create the heap, then call extract_max k times to get the kth largest.

4

Print the kth largest element

Print the value of the variable kth_largest using printf.

DSA C

int numbers[] = {20, 15, 30, 5, 10, 25, 35};
int k = 3;

int heap_size = 7;

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

void max_heapify(int arr[], int size, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left  arr[largest]) {
        largest = left;
    }
    if (right  arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        max_heapify(arr, size, largest);
    }
}

void build_max_heap(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        max_heapify(arr, size, i);
    }
}

int extract_max(int arr[], int *size) {
    int max = arr[0];
    arr[0] = arr[*size - 1];
    (*size)--;
    max_heapify(arr, *size, 0);
    return max;
}

int kth_largest = 0;
build_max_heap(numbers, heap_size);
for (int i = 0; i < k; i++) {
    kth_largest = extract_max(numbers, &heap_size);
}
// Print kth_largest below
# Your code here

Hint

Use printf("%d\n", kth_largest); to print the result.

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