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);