Kth Largest Element Using Max Heap in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two integers using pointers.

DSA C

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

Drag options to blanks, or click blank then click option'

Atemp

B*a

C*b

Da

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning *a = temp instead of *a = *b

Using a or b instead of *a or *b

To swap values, assign *a = *b and *b = temp. Here, *a = *b is needed.

2fill in blank

medium

Complete the code to heapify the subtree rooted at index i in max heap.

DSA C

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

    if (left < n && arr[left] [1] arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        maxHeapify(arr, n, largest);
    }
}

Drag options to blanks, or click blank then click option'

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causing min heap behavior

Using '==' which doesn't update largest

To maintain max heap, if left child is greater than current largest, update largest to left.

3fill in blank

hard

Fix the error in the code to build a max heap from an array.

DSA C

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

Drag options to blanks, or click blank then click option'

AbuildMaxHeap

BmaxHeapify

Cswap

DheapSort

Attempts:

3 left

💡 Hint

Common Mistakes

Calling buildMaxHeap recursively causing infinite loop

Calling swap instead of maxHeapify

To build max heap, call maxHeapify on each non-leaf node.

4fill in blank

hard

Fill both blanks to extract the kth largest element using max heap.

DSA C

int extractMax(int arr[], int *n) {
    if (*n <= 0)
        return -1;
    int max = arr[0];
    arr[0] = arr[[1]];
    (*n)--;
    maxHeapify(arr, *n, [2]);
    return max;
}

Drag options to blanks, or click blank then click option'

A*n - 1

B0

C1

D*n

Attempts:

3 left

💡 Hint

Common Mistakes

Using *n instead of *n - 1 causing out-of-bounds access

Heapifying from wrong index

Replace root with last element at index n-1, then heapify from root index 0.

5fill in blank

hard

Fill all three blanks to find the kth largest element using max heap.

DSA C

int kthLargest(int arr[], int n, int k) {
    buildMaxHeap(arr, n);
    int size = n;
    int result = -1;
    for (int i = 0; i < [1]; i++) {
        result = extractMax(arr, &[2]);
    }
    return [3];
}

Drag options to blanks, or click blank then click option'

Ak

Bsize

Cresult

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Looping n times instead of k

Passing n instead of size to extractMax

Returning size or n instead of result

Loop k times, extract max from heap reducing size, return last extracted value.

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