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