How to use a Min-Heap (Priority Queue) In Javascript
In this approach, we use a Min-Heap (Priority Queue) to keep track of the largest three elements as we iterate through the array. The idea is to maintain a heap of size 3. For every element in the array, we check if it’s larger than the smallest element in the heap (the root of the Min-Heap). If it is, we remove the smallest element and insert the current element into the heap.
Example: This example demonstrates finding the largest three elements in an array by using a Min-Heap to maintain the three largest elements in JavaScript.
class MinHeap {
constructor() {
this.heap = [];
}
insert(val) {
this.heap.push(val);
this.bubbleUp();
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
let element = this.heap[index];
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (parent <= element) break;
this.heap[index] = parent;
this.heap[parentIndex] = element;
index = parentIndex;
}
}
extractMin() {
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown(0);
}
return min;
}
sinkDown(index) {
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 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;
}
}
size() {
return this.heap.length;
}
peek() {
return this.heap[0];
}
}
function findLargestThreeElementsUsingMinHeap(arr) {
const minHeap = new MinHeap();
for (let num of arr) {
if (minHeap.size() < 3) {
minHeap.insert(num);
} else if (num > minHeap.peek()) {
minHeap.extractMin();
minHeap.insert(num);
}
}
const [thirdLargestEle, secondLargestEle, firstLargestEle] = minHeap.heap.sort((a, b) => a - b);
return {
"First Largest Element in Array": firstLargestEle,
"Second Largest Element in Array": secondLargestEle,
"Third Largest Element in Array": thirdLargestEle,
};
}
const inputArray = [12, 56, 7, 89, 43, 21];
const outputElements = findLargestThreeElementsUsingMinHeap(inputArray);
console.log(outputElements);
JavaScript Program to Find the Largest Three Elements in an Array
In this article, we are given an array of numbers, we need to find the largest three elements in an array in JavaScript. We will explore the easiest and most efficient code of each approach and also go through the output of the code.