Max Heap Approach

Brute Force Approach

Store the elements of the linked list in a priority queue (max heap). Pop out the elements from the heap till N becomes 0 and add it to an array. Return the array as our answer.

Example: The below example find N largest elements from a linked list in JavaScript.

Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}
function createLinkedList(arr) {
    if (arr.length === 0) {
        return null;
    }
 
    let head = new Node(arr[0]);
    let current = head;
 
    for (let i = 1; i < arr.length; i++) {
        current.next = new Node(arr[i]);
        current = current.next;
    }
 
    return head;
}
 
class MinHeap {
    constructor() {
        this.heap = [];
    }
 
    insert(value) {
        this.heap.push(value);
        this.heapifyUp(this.heap.length - 1);
    }
 
    heapifyUp(index) {
        let parentIndex = Math.floor((index - 1) / 2);
        while (parentIndex >= 0 && 
               this.heap[parentIndex] > 
               this.heap[index]) {
            [this.heap[parentIndex], this.heap[index]] = 
            [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
            parentIndex = Math.floor((index - 1) / 2);
        }
    }
 
    extractMin() {
        if (this.heap.length === 0) 
            return null;
        if (this.heap.length === 1) 
            return this.heap.pop();
 
        const minValue = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);
        return minValue;
    }
 
    heapifyDown(index) {
        let leftChildIndex = 2 * index + 1;
        let rightChildIndex = 2 * index + 2;
        let smallestIndex = index;
 
        if (leftChildIndex < this.heap.length && 
            this.heap[leftChildIndex] < 
            this.heap[smallestIndex]) {
            smallestIndex = leftChildIndex;
        }
        if (rightChildIndex < this.heap.length && 
            this.heap[rightChildIndex] < 
            this.heap[smallestIndex]) {
            smallestIndex = rightChildIndex;
        }
 
        if (smallestIndex !== index) {
            [this.heap[index], this.heap[smallestIndex]] = 
            [this.heap[smallestIndex], this.heap[index]];
            this.heapifyDown(smallestIndex);
        }
    }
}
 
function findNLargestElements(head, N) {
    const minHeap = new MinHeap();
    let current = head;
 
    while (current) {
        minHeap.insert(current.value);
        if (minHeap.heap.length > N) {
            minHeap.extractMin();
        }
        current = current.next;
    }
 
    const result = [];
    while (minHeap.heap.length > 0) {
        result.unshift(minHeap.extractMin());
    }
 
    return result;
}
 
const linkedList = 
    createLinkedList([22, 555, 324, 1, 60, 2]);
const N = 3;
console.log(`Top ${N} largest elements:`);
const largestElements = 
    findNLargestElements(linkedList, N);
console.log(largestElements);

Output

Top 3 largest elements:
[ 555, 324, 60 ]

JavaScript Program to Find N Largest Elements from a Linked List

This JavaScript program is designed to identify the N largest elements from a linked list. A linked list is a linear data structure where elements, known as nodes, are connected via pointers.

The program iterates through the linked list to determine the N largest elements it contains.

Table of Content

Brute Force Approach
Max Heap Approach

Tags:

#JavaScript-Program #JavaScript #Web Technologies

Brute Force Approach

Max Heap Approach

Javascript

JavaScript Program to Find N Largest Elements from a Linked List

Similar Reads