Max Heap

Intuition

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.

Algorithm

Create a max heap (priority queue) to store the elements of the linked list.
Iterate through the linked list from head to end.
For each element, insert the data into the heap.
Initialize an empty vector to store our answer.
Pop out N elements from the max-heap and add it to the vector or array.
Return the array and print the answer.

Code

C++

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Define a linked list node structure
class Node {
public:
    int data;
    Node* next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
 
// Function to find N largest elements
vector<int> findNLargestElements(Node* head, int N)
{
    // Create a max-heap
    priority_queue<int, vector<int> > pq;
 
    // Traverse the linked list and insert elements into the
    // maxHeap
    while (head != NULL) {
        pq.push(head->data);
        head = head->next;
    }
 
    // Pop N largest elements from the maxHeap
    vector<int> result;
    for (int i = 0; i < N; i++) {
        if (!pq.empty()) {
            result.push_back(pq.top());
            pq.pop();
        }
    }
 
    return result;
}
 
// Function to print a vector
void print(vector<int>& v)
{
    for (int num : v) {
        cout << num << " ";
    }
    cout << endl;
}
 
// Define a function to insert a node at the beginning of
// the linked list
void insertAtTheBegin(Node** head, int data)
{
    Node* newNode = new Node(data);
    newNode->next = *head;
    *head = newNode;
}
 
int main()
{
    int arr[] = { 81, 52, 45, 10, 3, 2, 96 };
    int N = 3;
    int list_size = sizeof(arr) / sizeof(arr[0]);
 
    // Start with an empty linked list
    Node* start = nullptr;
 
    // Create a linked list from the array
    for (int i = list_size - 1; i >= 0; i--) {
        insertAtTheBegin(&start, arr[i]);
    }
 
    vector<int> result = findNLargestElements(start, N);
    cout << "Output: ";
    print(result);
 
    return 0;
}
 
// This code is contributed by Abhinav Mahajan (abhinav_m22)

Java

import java.util.PriorityQueue;
import java.util.Vector;
 
// Define a linked list node structure
class Node {
    public int data;
    public Node next;
 
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
 
public class Main {
    // Function to find N largest elements
    static Vector<Integer> findNLargestElements(Node head, int N) {
        // Create a max-heap
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
 
        // Traverse the linked list and insert elements into the maxHeap
        while (head != null) {
            pq.add(head.data);
            head = head.next;
        }
 
        // Pop N largest elements from the maxHeap
        Vector<Integer> result = new Vector<>();
        for (int i = 0; i < N; i++) {
            if (!pq.isEmpty()) {
                result.add(pq.poll());
            }
        }
 
        return result;
    }
 
    // Function to print a vector
    static void print(Vector<Integer> v) {
        for (int num : v) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
 
    // Function to insert a node at the beginning of the linked list
    static Node insertAtTheBegin(Node head, int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        return newNode;
    }
 
    public static void main(String[] args) {
        int[] arr = { 81, 52, 45, 10, 3, 2, 96 };
        int N = 3;
        int list_size = arr.length;
 
        // Start with an empty linked list
        Node start = null;
 
        // Create a linked list from the array
        for (int i = list_size - 1; i >= 0; i--) {
            start = insertAtTheBegin(start, arr[i]);
        }
 
        Vector<Integer> result = findNLargestElements(start, N);
        System.out.print("Output: ");
        print(result);
    }
}

Python3

import heapq
 
# Define a linked list node class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Function to find N largest elements
def find_n_largest_elements(head, N):
    # Create a max heap
    max_heap = []
 
    # Traverse the linked list and insert elements into the max heap
    while head:
        heapq.heappush(max_heap, -head.data)
        head = head.next
 
    # Pop N largest elements from the max heap
    result = []
    for i in range(N):
        if max_heap:
            result.append(-heapq.heappop(max_heap))
 
    return result
 
# Function to print a list
def print_list(lst):
    print(" ".join(map(str, lst)))
 
# Function to insert a node at the beginning of the linked list
def insert_at_the_begin(head, data):
    new_node = Node(data)
    new_node.next = head
    return new_node
 
if __name__ == "__main__":
    arr = [81, 52, 45, 10, 3, 2, 96]
    N = 3
 
    # Start with an empty linked list
    start = None
 
    # Create a linked list from the array
    for i in range(len(arr) - 1, -1, -1):
        start = insert_at_the_begin(start, arr[i])
 
    result = find_n_largest_elements(start, N)
    print("Output:", end=" ")
    print_list(result)

C#

using System;
using System.Collections.Generic;
 
// Define a linked list node structure
public class Node
{
    public int data;
    public Node next;
 
    public Node(int data)
    {
        this.data = data;
        this.next = null;
    }
}
 
public class Program
{
    // Function to find N largest elements
    public static List<int> FindNLargestElements(Node head, int N)
    {
        // Create a max-heap by implementing a min-heap with reversed ordering
        var pq = new PriorityQueue<int>((x, y) => y.CompareTo(x));
 
        // Traverse the linked list and insert elements into the maxHeap
        while (head != null)
        {
            pq.Enqueue(head.data);
            head = head.next;
        }
 
        // Pop N largest elements from the maxHeap
        var result = new List<int>();
        for (int i = 0; i < N; i++)
        {
            if (pq.Count > 0)
            {
                result.Add(pq.Dequeue());
            }
        }
 
        return result;
    }
 
    // Function to print a list
    public static void Print(List<int> list)
    {
        foreach (var num in list)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
 
    // Define a function to insert a node at the beginning of the linked list
    public static void InsertAtTheBegin(ref Node head, int data)
    {
        var newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
 
    public static void Main()
    {
        int[] arr = { 81, 52, 45, 10, 3, 2, 96 };
        int N = 3;
 
        Node start = null;
 
        // Create a linked list from the array
        for (int i = arr.Length - 1; i >= 0; i--)
        {
            InsertAtTheBegin(ref start, arr[i]);
        }
 
        var result = FindNLargestElements(start, N);
        Console.Write("Output: ");
        Print(result);
    }
}
 
// Implement a priority queue for the C# code
public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> data;
    private Comparison<T> comparison;
 
    public PriorityQueue(Comparison<T> comparison)
    {
        this.data = new List<T>();
        this.comparison = comparison;
    }
 
    public void Enqueue(T item)
    {
        data.Add(item);
        int childIndex = data.Count - 1;
        while (childIndex > 0)
        {
            int parentIndex = (childIndex - 1) / 2;
            if (comparison(data[childIndex], data[parentIndex]) >= 0)
                break;
            T tmp = data[childIndex];
            data[childIndex] = data[parentIndex];
            data[parentIndex] = tmp;
            childIndex = parentIndex;
        }
    }
 
    public T Dequeue()
    {
        int lastIndex = data.Count - 1;
        T frontItem = data[0];
        data[0] = data[lastIndex];
        data.RemoveAt(lastIndex--);
 
        int parentIndex = 0;
        while (true)
        {
            int leftChildIndex = parentIndex * 2 + 1;
            if (leftChildIndex > lastIndex)
                break;
            int rightChildIndex = leftChildIndex + 1;
            if (rightChildIndex <= lastIndex && comparison(data[rightChildIndex], data[leftChildIndex]) < 0)
                leftChildIndex = rightChildIndex;
            if (comparison(data[parentIndex], data[leftChildIndex]) <= 0)
                break;
            T tmp = data[parentIndex];
            data[parentIndex] = data[leftChildIndex];
            data[leftChildIndex] = tmp;
            parentIndex = leftChildIndex;
        }
        return frontItem;
    }
 
    public int Count
    {
        get { return data.Count; }
    }
}
 
 
// This code is contributed by shivamgupta310570

Javascript

// Define a linked list node structure
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
 
// Function to find N largest elements
function findNLargestElements(head, N) {
    // Create a max-heap
    const pq = new PriorityQueue((a, b) => b - a);
 
    // Traverse the linked list and insert elements into the maxHeap
    while (head !== null) {
        pq.add(head.data);
        head = head.next;
    }
 
    // Pop N largest elements from the maxHeap
    const result = [];
    for (let i = 0; i < N; i++) {
        if (!pq.isEmpty()) {
            result.push(pq.poll());
        }
    }
 
    return result;
}
 
// Function to insert a node at the beginning of the linked list
function insertAtTheBegin(head, data) {
    const newNode = new Node(data);
    newNode.next = head;
    return newNode;
}
 
// Function to print an array
function print(arr) {
    for (const num of arr) {
        process.stdout.write(num + ' ');
    }
    console.log();
}
 
// Priority Queue implementation
class PriorityQueue {
    constructor(compareFunction) {
        this.queue = [];
        this.compare = compareFunction || ((a, b) => a - b);
    }
 
    add(element) {
        this.queue.push(element);
        this.queue.sort(this.compare);
    }
 
    poll() {
        return this.queue.shift();
    }
 
    isEmpty() {
        return this.queue.length === 0;
    }
}
 
// Main function
function main() {
    const arr = [81, 52, 45, 10, 3, 2, 96];
    const N = 3;
    const listSize = arr.length;
 
    // Start with an empty linked list
    let start = null;
 
    // Create a linked list from the array
    for (let i = listSize - 1; i >= 0; i--) {
        start = insertAtTheBegin(start, arr[i]);
    }
 
    const result = findNLargestElements(start, N);
    process.stdout.write("Output: ");
    print(result);
}
 
// Run the main function
main();

Output

Output: 96 81 52

Time Complexity: O(N*logN). To insert elements into the max-heap, it takes logN time. We insert N elements from the linked list to the heap, hence the overall time complexity is O(N*logN).

Space Complexity: O(N). We create a max-heap data structure due to which it requires O(N) space.