Kth Largest Element Using Max Heap in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a max heap?

A max heap is a special tree-based data structure where the parent node is always greater than or equal to its children. This means the largest element is always at the root.

beginner

How does a max heap help find the kth largest element?

By building a max heap from the array, the largest element is at the root. Removing the root k-1 times and then looking at the root gives the kth largest element.

intermediate

What is the time complexity of building a max heap from an array of size n?

Building a max heap from an array takes O(n) time.

intermediate

What is the time complexity of extracting the max element from a max heap?

Extracting the max element (root) from a max heap takes O(log n) time because the heap needs to be restructured to maintain the heap property.

beginner

Explain the steps to find the kth largest element using a max heap.

1. Build a max heap from the array.
2. Extract the max element (root) k-1 times.
3. The root after these extractions is the kth largest element.

What property does a max heap maintain?

A Parent node is greater than or equal to children

B Parent node is less than or equal to children

C All nodes have equal values

D Nodes are sorted in ascending order

A max heap always keeps the parent node greater than or equal to its children.

What is the root of a max heap?

A Smallest element

B Random element

C Median element

D Largest element

The root of a max heap is the largest element in the heap.

How many times do you extract the max element to find the kth largest element?

A k times

B k-1 times

C 1 time

D n times

You extract the max element k-1 times; the next root is the kth largest.

What is the time complexity of extracting the max element from a max heap of size n?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Extracting the max element requires restructuring the heap, which takes O(log n) time.

What is the first step to find the kth largest element using a max heap?

A Sort the array

B Reverse the array

C Build a max heap from the array

D Extract the min element

You first build a max heap from the array to access the largest elements efficiently.

Describe how to find the kth largest element using a max heap.

Think about how the largest elements are arranged in a max heap.

Explain why extracting the max element from a max heap takes O(log n) time.

Consider the steps needed to keep the heap valid after removal.

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