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

Kth Largest Element Using Max Heap

📖 Scenario: You are working on a system that needs to find the kth largest number from a list of scores quickly. Using a max heap is a great way to do this efficiently.

🎯 Goal: Build a TypeScript program that uses a max heap to find the kth largest element from a given list of numbers.

📋 What You'll Learn

Create an array called numbers with the exact values: [3, 1, 5, 12, 10, 7]

Create a variable called k and set it to 3

Implement a max heap using a class called MaxHeap with methods to insert and extract the maximum element

Use the max heap to find the kth largest element from numbers

Print the kth largest element

💡 Why This Matters

🌍 Real World

Finding the kth largest element is common in ranking systems, like finding the third highest score in a game leaderboard.

💼 Career

Understanding heaps and priority queues is important for software engineers working on performance-critical applications such as search engines, recommendation systems, and real-time analytics.

1

Create the numbers array

Create an array called numbers with these exact values: [3, 1, 5, 12, 10, 7]

DSA Typescript

# Your code here

Hint

Use const numbers = [3, 1, 5, 12, 10, 7]; to create the array.

2

Set the value of k

Create a variable called k and set it to 3

DSA Typescript

const numbers = [3, 1, 5, 12, 10, 7];
# Your code here

Hint

Use const k = 3; to set the value.

3

Implement the MaxHeap class and build the heap

Create a class called MaxHeap with methods insert and extractMax. Then create an instance called maxHeap and insert all numbers from numbers into it using a for loop with variable num.

DSA Typescript

const numbers = [3, 1, 5, 12, 10, 7];
const k = 3;
// Your code here

Hint

Define the MaxHeap class with insert and extractMax methods. Then insert each number from numbers using a for loop.

4

Find and print the kth largest element

Use a for loop with variable i from 1 to k to extract the maximum element from maxHeap. Store the extracted value in a variable called kthLargest. Then print kthLargest.

DSA Typescript

const numbers = [3, 1, 5, 12, 10, 7];
const k = 3;

class MaxHeap {
    heap: number[] = [];

    insert(value: number) {
        this.heap.push(value);
        this.bubbleUp();
    }

    bubbleUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] >= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    extractMax(): number | undefined {
        if (this.heap.length === 0) return undefined;
        if (this.heap.length === 1) return this.heap.pop();
        const max = this.heap[0];
        this.heap[0] = this.heap.pop()!;
        this.sinkDown(0);
        return max;
    }

    sinkDown(index: number) {
        const length = this.heap.length;
        const element = this.heap[index];
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swapIndex: number | null = null;

            if (leftChildIndex  element) {
                    swapIndex = leftChildIndex;
                }
            }

            if (rightChildIndex  element) || (swapIndex !== null && rightChild > leftChild!)) {
                    swapIndex = rightChildIndex;
                }
            }

            if (swapIndex === null) break;

            this.heap[index] = this.heap[swapIndex];
            this.heap[swapIndex] = element;
            index = swapIndex;
        }
    }
}

const maxHeap = new MaxHeap();
for (const num of numbers) {
    maxHeap.insert(num);
}

# Your code here

Hint

Extract the max element k times from the heap. The last extracted value is the kth largest. Print it using console.log(kthLargest);

Practice

1. What is the main idea behind finding the kth largest element using a max heap?

easy

A. Use a hash map to count frequencies and find the kth largest.

B. Sort the array and pick the element at index k.

C. Build a min heap and extract the minimum element k times.

D. Build a max heap from the array and extract the maximum element k times.

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

   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 D

4. Quick Check:

   Max heap extraction = kth largest element [OK]

Hint: Extract max from max heap k times to get kth largest [OK]

Common Mistakes:

• Using min heap instead of max heap
• Sorting instead of using heap
• Extracting fewer or more than k times

2. Which of the following TypeScript code snippets correctly creates a max heap from an array nums?

easy

A. const maxHeap = new MaxHeap(nums);

B. const maxHeap = new Heap(nums, (a, b) => a - b);

C. const maxHeap = new Heap(nums, (a, b) => b - a);

D. const maxHeap = new Heap(nums);

Solution

1. Step 1: Understand heap comparator

   To create a max heap, the comparator should order elements so that larger values come first, i.e., (a, b) => b - a.

2. Step 2: Check options

   const maxHeap = new Heap(nums, (a, b) => b - a); uses (a, b) => b - a, which correctly creates a max heap.

3. Final Answer:

   const maxHeap = new Heap(nums, (a, b) => b - a); -> Option C

4. Quick Check:

   Comparator b - a = max heap [OK]

Hint: Use comparator (a, b) => b - a for max heap [OK]

Common Mistakes:

• Using default comparator which creates min heap
• Reversing comparator incorrectly
• Assuming new MaxHeap() exists without comparator

3. What is the output of the following TypeScript code?

const nums = [3, 1, 5, 12, 2, 11];
const k = 3;
const maxHeap = new Heap(nums, (a, b) => b - a);
let kthLargest = null;
for (let i = 0; i < k; i++) {
  kthLargest = maxHeap.extract();
}
console.log(kthLargest);

medium

A. 5

B. 11

C. 3

D. 12

Solution

1. Step 1: Build max heap from array

   Max heap order: root is largest element. Initial max is 12, then 11, then 5.

2. Step 2: Extract max k=3 times

   Extract 1: 12, Extract 2: 11, Extract 3: 5. So kthLargest is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   3rd largest in [3,1,5,12,2,11] = 5 [OK]

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

Common Mistakes:

• Confusing 3rd largest with 3rd smallest
• Extracting fewer than k times
• Not building max heap correctly

4. Identify the bug in this TypeScript code that tries to find the kth largest element using a max heap:

const nums = [7, 10, 4, 3, 20, 15];
const k = 4;
const maxHeap = new Heap(nums, (a, b) => b - a);
let kthLargest = null;
for (let i = 0; i <= k; i++) {
  kthLargest = maxHeap.extract();
}
console.log(kthLargest);

medium

A. The comparator is wrong; should be (a, b) => a - b.

B. The loop runs one extra time; should be i < k not i <= k.

C. The heap is not built correctly from the array.

D. The variable kthLargest should be initialized to 0.

Solution

1. Step 1: Check loop condition

   The loop runs from i = 0 to i = k inclusive, so it runs k+1 times.

2. Step 2: Correct loop to run exactly k times

   It should run k times, so condition must be i < k.

3. Final Answer:

   Loop runs one extra time; should be i < k -> Option B

4. Quick Check:

   Loop runs k times to extract kth largest [OK]

Hint: Loop must run exactly k times, not k+1 [OK]

Common Mistakes:

• Using <= instead of < in loop
• Wrong comparator for max heap
• Initializing variables incorrectly

5. Given a large array nums with 1 million elements, which approach is most efficient to find the kth largest element when k is small (e.g., 10)?

hard

A. Build a min heap of size k and iterate through nums to maintain it.

B. Sort the entire array and pick the element at index length - k.

C. Use a hash map to count frequencies and find the kth largest.

D. Build a max heap of all elements and extract max k times.

Solution

1. Step 1: Analyze time complexity of building max heap

   Building max heap of 1 million elements is O(n), extracting k times is O(k log n), which is costly.

2. Step 2: Use min heap of size k

   Maintain a min heap of size k while iterating. This keeps top k largest elements efficiently in O(n log k).

3. Step 3: Compare with sorting

   Sorting entire array is O(n log n), slower than min heap approach for small k.

4. Final Answer:

   Build a min heap of size k and maintain it while iterating -> Option A

5. Quick Check:

   Min heap size k = efficient for small k [OK]

Hint: Use min heap of size k for large arrays and small k [OK]

Common Mistakes:

• Building max heap of entire array for large data
• Sorting entire array unnecessarily
• Ignoring heap size optimization