Heap sort for Linked List
Given a linked list, the task is to sort the linked list using HeapSort.
Examples:
Input: list = 7 -> 698147078 -> 1123629290 -> 1849873707 -> 1608878378 -> 140264035 -> -1206302000
Output: -1206302000 -> 7 -> 140264035 -> 1123629290 -> 1608878378 -> 1698147078 ->1849873707Input: list = 7 -> -1075222361 -> -1602192039 -> -1374886644 -> -1007110694 -> -95856765 -> -1739971780
Output: -1739971780 -> -1602192039 -> -1374886644 -> -1075222361 -> -1007110694 -> -95856765 -> 7
Approach: The idea to solve the problem using HeapSort is as follows:
Create an array of Node type from LinkedList and use the heapsort method as applied for normal arrays. The only difference is the usage of custom comparator for comparing the Nodes.
Follow the steps to solve the problem:
- Copy the Node data of the linked list to an array of Node type.
- Now use this array as source and sort the data using heapsort as applied in case of array.
- Use custom comparator to compare the Nodes.
- Since Node based array is being used, the data change effect will actually be on LinkedList but not on the array.
- Finally, print the data of the linked list.
Below is the implementation of the above approach:
C++
// C++ program for the above approach:#include <iostream>#include <cstdlib>using namespace std;#define SIZE 7using namespace std;// Node class to describe basic node structureclass LinkedListNode {public: int data; LinkedListNode *next; LinkedListNode(int data, LinkedListNode *node) { this->data = data; this->next = node; }};// sortByValueComparator implements// Comparator interface to sort the data.// Comparator sort the data on the basis// of returned value as mentioned below.// if return value < 0 that means// node1.data < node2.data// if return value > 0 that means// node1.data > node2.data// if return value = 0 that means// node1.data == node2.dataclass SortByValueComparator {public: int compare(LinkedListNode *node1, LinkedListNode *node2) { // If we interchange return value // -1 and 1 then LinkedList will be // sorted in reverse/descending order. if (node1->data < node2->data) { return -1; } else if (node1->data > node2->data) { return 1; } return 0; }};SortByValueComparator sortByValueComparator;// Function to heapifyvoid heapify(LinkedListNode **arr, int n, int i) { int largest = i; int right = 2 * i + 2; int left = 2 * i + 1; // Check if left child is larger // than root if (left < n && sortByValueComparator.compare(arr[left], arr[largest]) > 0) { largest = left; } // Check if right child is larger // than the largest till now if (right < n && sortByValueComparator.compare(arr[right], arr[largest]) > 0) { largest = right; } // swap if largest is not root if (largest != i) { int swap = arr[i]->data; arr[i]->data = arr[largest]->data; arr[largest]->data = swap; // Recursively heapify the subTree heapify(arr, n, largest); }}// Function to sort the arrayvoid sortArray(LinkedListNode **arr, int n) { // Build heap for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // Moving current root to end for (int i = n - 1; i > 0; i--) { int temp = arr[0]->data; arr[0]->data = arr[i]->data; arr[i]->data = temp; heapify(arr, i, 0); }} // Function to utilise the heapsortvoid heapsort(LinkedListNode *node) { LinkedListNode *head = node; int i = 0; // Array to copy the linked list data LinkedListNode **arr = new LinkedListNode *[SIZE]; while (head != nullptr) { arr[i] = head; i++; head = head->next; } sortArray(arr, SIZE); cout << "\nLinkedList after sorting: "; for (int i = 0; i < SIZE; i++) { cout << arr[i]->data << " "; } delete[] arr;}// Method that will return a random// LinkedList of size = 6.LinkedListNode *createLinkedList() { srand(time(nullptr)); LinkedListNode *head = new LinkedListNode(SIZE, nullptr); LinkedListNode *node = head; for (int i = SIZE - 1; i > 0; i--) { node->next = new LinkedListNode(rand() % 101, nullptr); node = node->next; } cout << "LinkedList before sorting: "; node = head; while (node != nullptr) { cout << node->data << " "; node = node->next; } return head;}// Driver codeint main() { // Driver code LinkedListNode *node = createLinkedList(); // Function call heapsort(node); return 0;}// this code is contributed by bhardwajji |
Java
// JAVA program for the above approach:import java.util.Arrays;import java.util.Comparator;import java.util.Random;// Node class to describe// basic node structureclass LinkedListNode { int data; LinkedListNode next; LinkedListNode(int data, LinkedListNode node) { this.data = data; next = node; }}public class GFG2 { private static final int SIZE = 7; private static final SortByValueComparator sortByValueComparator = new SortByValueComparator(); // Function to utilise the heapsort public static void heapsort(LinkedListNode node) { LinkedListNode head = node; int i = 0; // Array to copy the linked list data LinkedListNode[] arr = new LinkedListNode[SIZE]; while (head != null) { arr[i++] = head; head = head.next; } sortArray(arr); System.out.println("\nLinkedList after sorting: "); while (node != null) { System.out.print(node.data + " "); node = node.next; } } // Function to sort the array public static void sortArray(LinkedListNode[] arr) { int n = arr.length; // Build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i > 0; i--) { // Moving current root to end int temp = arr[0].data; arr[0].data = arr[i].data; arr[i].data = temp; heapify(arr, i, 0); } } // Method that will return a random // LinkedList of size = 6. public static LinkedListNode createLinkedList() { Random random = new Random(); LinkedListNode head = new LinkedListNode(SIZE, null); LinkedListNode node = head; for (int i = SIZE - 1; i > 0; i--) { node.next = new LinkedListNode(random.nextInt(), null); node = node.next; } System.out.println("LinkedList before sorting: "); node = head; while (node != null) { System.out.print(node.data + " "); node = node.next; } return head; } // Function to heapify private static void heapify(LinkedListNode[] arr, int n, int i) { int largest = i; int right = 2 * i + 2; int left = 2 * i + 1; // Check if left child is larger // than root if (left < n && sortByValueComparator.compare(arr[left], arr[largest]) > 0) largest = left; // Check if right child is larger // than the largest till now if (right < n && sortByValueComparator.compare(arr[right], arr[largest]) > 0) largest = right; // Swap if largest is not root if (largest != i) { int swap = arr[i].data; arr[i].data = arr[largest].data; arr[largest].data = swap; // Recursively heapify the subTree heapify(arr, n, largest); } } // Driver code public static void main(String[] args) { LinkedListNode node = createLinkedList(); // Function call heapsort(node); }}// sortByValueComparator implements// Comparator interface to sort the data.// Comparator sort the data on the basis// of returned value as mentioned below.// if return value < 0 that means// node1.data < node2.data// if return value > 0 that means// node1.data > node2.data// if return value = 0 that means// node1.data == node2.dataclass SortByValueComparator implements Comparator<LinkedListNode> { public int compare(LinkedListNode node1, LinkedListNode node2) { // If we interchange return value // -1 and 1 then LinkedList will be // sorted in reverse/descending order. if (node1.data < node2.data) { return -1; } else if (node1.data > node2.data) { return 1; } return 0; }} |
Python3
import random# Node class to describe basic node structureclass LinkedListNode: def __init__(self, data, node): self.data = data self.next = node# SortByValueComparator implements Comparator interface to sort the data.# Comparator sort the data on the basis of returned value as mentioned below.# if return value < 0 that means node1.data < node2.data# if return value > 0 that means node1.data > node2.data# if return value = 0 that means node1.data == node2.dataclass SortByValueComparator: def compare(self, node1, node2): # If we interchange return value -1 and 1 then LinkedList will be # sorted in reverse/descending order. if node1.data < node2.data: return -1 elif node1.data > node2.data: return 1 return 0# Function to sort the arraydef sortArray(arr): n = len(arr) # Build heap for i in range(n//2-1, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Moving current root to end temp = arr[0].data arr[0].data = arr[i].data arr[i].data = temp heapify(arr, i, 0)# Function to heapifydef heapify(arr, n, i): largest = i right = 2 * i + 2 left = 2 * i + 1 # Check if left child is larger than root if left < n and sortByValueComparator.compare(arr[left], arr[largest]) > 0: largest = left # Check if right child is larger than the largest till now if right < n and sortByValueComparator.compare(arr[right], arr[largest]) > 0: largest = right # Swap if largest is not root if largest != i: swap = arr[i].data arr[i].data = arr[largest].data arr[largest].data = swap # Recursively heapify the subTree heapify(arr, n, largest)# Function to utilise the heapsortdef heapsort(node): head = node i = 0 # Array to copy the linked list data arr = [None] * SIZE while head != None: arr[i] = head i += 1 head = head.next sortArray(arr) print("\nLinkedList after sorting: ") while node != None: print(node.data, end=" ") node = node.next# Method that will return a random LinkedList of size = 6.def createLinkedList(): random.seed() head = LinkedListNode(SIZE, None) node = head for i in range(SIZE-1, 0, -1): node.next = LinkedListNode(random.randint(0, 100), None) node = node.next print("LinkedList before sorting: ") node = head while node != None: print(node.data, end=" ") node = node.next return headSIZE = 7sortByValueComparator = SortByValueComparator()# Driver codenode = createLinkedList()# Function callheapsort(node) |
Javascript
// Node class to describe basic node structureclass LinkedListNode { constructor(data, node) { this.data = data; this.next = node; }}// SortByValueComparator implements Comparator interface to sort the data.// Comparator sort the data on the basis of returned value as mentioned below.// if return value < 0 that means node1.data < node2.data// if return value > 0 that means node1.data > node2.data// if return value = 0 that means node1.data == node2.dataclass SortByValueComparator { compare(node1, node2) { // If we interchange return value -1 and 1 then LinkedList will be // sorted in reverse/descending order. if (node1.data < node2.data) { return -1; } else if (node1.data > node2.data) { return 1; } return 0; }}// Function to sort the arrayfunction sortArray(arr) { const n = arr.length; // Build heap for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(arr, n, i); } for (let i = n - 1; i > 0; i--) { // Moving current root to end const temp = arr[0].data; arr[0].data = arr[i].data; arr[i].data = temp; heapify(arr, i, 0); }}// Function to heapifyfunction heapify(arr, n, i) { let largest = i; const right = 2 * i + 2; const left = 2 * i + 1; // Check if left child is larger than root if (left < n && sortByValueComparator.compare(arr[left], arr[largest]) > 0) { largest = left; } // Check if right child is larger than the largest till now if (right < n && sortByValueComparator.compare(arr[right], arr[largest]) > 0) { largest = right; } // Swap if largest is not root if (largest !== i) { const swap = arr[i].data; arr[i].data = arr[largest].data; arr[largest].data = swap; // Recursively heapify the subTree heapify(arr, n, largest); }}// Function to utilise the heapsortfunction heapsort(node) { let head = node; let i = 0; // Array to copy the linked list data const arr = new Array(SIZE); while (head !== null) { arr[i] = head; i++; head = head.next; } sortArray(arr); console.log("\nLinkedList after sorting: "); let current = node; let ans=""; while (current !== null) { ans=ans+current.data+" "; current = current.next; } console.log(ans);}// Method that will return a random LinkedList of size = 6.function createLinkedList() { const head = new LinkedListNode(SIZE, null); let node = head; for (let i = SIZE - 1; i > 0; i--) { node.next = new LinkedListNode(Math.floor(Math.random() * 101), null); node = node.next; } console.log("LinkedList before sorting: "); node = head; let anss=""; while (node !== null) { anss = anss+ node.data+" "; node = node.next; } console.log(anss);return head; }let SIZE = 7;let sortByValueComparator = new SortByValueComparator()// Driver codenode = createLinkedList()// Function callheapsort(node) |
C#
using System;using System.Collections.Generic;using System.Collections;using System.Linq;// C# program for the above approach:// Node class to describe// basic node structureclass LinkedListNode { public int data; public LinkedListNode next; public LinkedListNode(int d, LinkedListNode node) { data = d; next = node; }}// sortByValueComparator implements// Comparator interface to sort the data.// Comparator sort the data on the basis// of returned value as mentioned below.// if return value < 0 that means// node1.data < node2.data// if return value > 0 that means// node1.data > node2.data// if return value = 0 that means// node1.data == node2.dataclass SortByValueComparator { public int compare(LinkedListNode node1, LinkedListNode node2) { // If we interchange return value // -1 and 1 then LinkedList will be // sorted in reverse/descending order. if (node1.data < node2.data) { return -1; } else if (node1.data > node2.data) { return 1; } return 0; }}class HelloWorld { public static int SIZE = 7; private static SortByValueComparator sortByValueComparator = new SortByValueComparator(); // Function to utilise the heapsort public static void heapsort(LinkedListNode node) { LinkedListNode head = node; int i = 0; // Array to copy the linked list data LinkedListNode[] arr = new LinkedListNode[SIZE]; while (head != null) { arr[i++] = head; head = head.next; } sortArray(arr); Console.WriteLine("\nLinkedList after sorting: "); while (node != null) { Console.Write(node.data + " "); node = node.next; } } // Function to sort the array public static void sortArray(LinkedListNode[] arr) { int n = arr.Length; // Build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i > 0; i--) { // Moving current root to end int temp = arr[0].data; arr[0].data = arr[i].data; arr[i].data = temp; heapify(arr, i, 0); } } // Method that will return a random // LinkedList of size = 6. public static LinkedListNode createLinkedList() { Random random = new Random(); LinkedListNode head = new LinkedListNode(SIZE, null); LinkedListNode node = head; for (int i = SIZE - 1; i > 0; i--) { node.next = new LinkedListNode(random.Next(), null); node = node.next; } Console.WriteLine("LinkedList before sorting: "); node = head; while (node != null) { Console.Write(node.data + " "); node = node.next; } return head; } // Function to heapify private static void heapify(LinkedListNode[] arr, int n, int i) { int largest = i; int right = 2 * i + 2; int left = 2 * i + 1; // Check if left child is larger // than root if (left < n && sortByValueComparator.compare(arr[left], arr[largest]) > 0) largest = left; // Check if right child is larger // than the largest till now if (right < n && sortByValueComparator.compare(arr[right], arr[largest]) > 0) largest = right; // Swap if largest is not root if (largest != i) { int swap = arr[i].data; arr[i].data = arr[largest].data; arr[largest].data = swap; // Recursively heapify the subTree heapify(arr, n, largest); } } static void Main() { LinkedListNode node = createLinkedList(); // Function call heapsort(node); }}// The code is contributed by Nidhi goel. |
Output
LinkedList before sorting: 7 -126832807 1771004780 1641683278 -179100326 -311811843 1468066971 LinkedList after sorting: -311811843 -179100326 -126832807 7 1468066971 1641683278 1771004780
Time Complexity: O(N * logN), where N is the number of nodes in the given LinkedList.
Auxiliary Space: O(N), for creating an additional array to store the given nodes.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
