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
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.
Example: The below example uses the sort method to sort an array of numbers in descending order and returns the top ‘k’ elements.
function topKElementsSorting(arr, k) {
arr.sort((a, b) => b - a);
return arr.slice(0, k);
}
// Example
const arr = [3, 1, 4, 2, 3, 4, 4];
const k = 3;
console.log("Top", k, "elements:",
topKElementsSorting(arr, k));
Output
Top 3 elements: [ 4, 4, 4 ]
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.
Example: The below example uses the max heap method to find the top ‘k’ elements from an array.
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 ]
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.
Example: The below example uses quick select algorithm to efficiently find the top ‘k’ elements from an array.
function partition(arr, left, right) {
const pivot = arr[right];
let i = left - 1;
for (let j = left; j < right; j++) {
if (arr[j] >= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[right]] =
[arr[right], arr[i + 1]];
return i + 1;
}
function quickSelect(arr, left, right, k) {
const pivotIndex = partition(arr, left, right);
if (pivotIndex === k)
return arr.slice(0, k);
else if (pivotIndex < k)
return quickSelect(arr, pivotIndex + 1, right, k);
else
return quickSelect(arr, left, pivotIndex - 1, k);
}
function topKElementsQuickSelect(arr, k) {
return quickSelect(arr, 0, arr.length - 1, k);
}
const arr = [3, 1, 4, 2, 3, 4, 4];
const k = 3;
console.log("Top", k, "elements:", topKElementsQuickSelect(arr, k));
Output
Top 3 elements: [ 4, 4, 4 ]
Contact Us