How to use a Max Heap In Javascript

In this approach, the max heap method is used to define a MaxHeap class for inserting and extracting maximum values. The topKElementsMaxHeap function creates a max heap from the input array and extracts the top ‘k’ elements using the max heap method.

Example: The below example uses the max heap method to find the top ‘k’ elements from an array.

JavaScript
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    insert(val) {
        this.heap.push(val);
        this.heapifyUp();
    }

    heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            const 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() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return max;
    }

    heapifyDown() {
        let index = 0;
        const length = this.heap.length;
        const element = this.heap[0];
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild > element) {
                    swap = leftChildIndex;
                }
            }
            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if ((swap === null && rightChild > element) 
                    || (swap !== null && rightChild > leftChild)) {
                    swap = rightChildIndex;
                }
            }
            if (swap === null) break;
            this.heap[index] = this.heap[swap];
            this.heap[swap] = element;
            index = swap;
        }
    }
}

function topKElementsMaxHeap(arr, k) {
    const heap = new MaxHeap();
    arr.forEach(num => heap.insert(num));
    const result = [];
    for (let i = 0; i < k; i++) {
        result.push(heap.extractMax());
    }
    return result;
}

// Example
const arr = [3, 1, 4, 2, 3, 4, 4];
const k = 3;
console.log("Top", k, "elements:", 
        topKElementsMaxHeap(arr, k));

Output
Top 3 elements: [ 4, 4, 4 ]

JavaScript Program to Find Top k Elements

Given an array, our task is to find the top k elements in an unsorted array of integers in JavaScript, either the largest or the smallest. Duplicate values may be in the array. The output will be a new array with the top k elements arranged in a non-ascending order (from largest to smallest).

Table of Content

  • Sorting an Array and Extracting the top k Elements
  • Using a Max Heap
  • Using Quickselect algorithm

Similar Reads

Sorting an Array and Extracting the top k Elements

In this approach, the unsorted array of integers is sorted in non-ascending order, from highest to lowest in JavaScript. Once the array is sorted, the top k elements are extracted by selecting the first k elements of the sorted array. Sorting the array allows for easy identification of the top aspects, as they are positioned at the beginning of the sorted array....

Using a Max Heap

In this approach, the max heap method is used to define a MaxHeap class for inserting and extracting maximum values. The topKElementsMaxHeap function creates a max heap from the input array and extracts the top ‘k’ elements using the max heap method....

Using Quickselect Algorithm

In this approach, the Quickselect algorithm is used to effectively identify the highest k elements from the unsorted array. We find the kth largest element by partitioning the array recursively based on a pivot element, which allows us to determine the top k elements....

Contact Us