In Java code implement the HeapSort algorithm Your function

In Java code, implement the HeapSort algorithm. Your function must take an ArrayList as input and output a sorted ArrayList. Allow the program to accept user input that becomes added to the ArrayList, if no elements are added by the user, handle the exception.

Solution

Hi, Please find my program.

Please let me know in case of any issue.

import java.util.ArrayList;

import java.util.Scanner;

//Java program for implementation of Heap Sort

public class HeapSort

{

   public void sort(ArrayList<Integer> list)

   {

       int n = list.size();

       // Build heap (relistange listay)

       for (int i = n / 2 - 1; i >= 0; i--)

           heapify(list, n, i);

       // One by one extract an element from heap

       for (int i=n-1; i>=0; i--)

       {

           // Move current root to end

           int temp = list.get(0);

           list.set(0, list.get(i));

           list.set(i, temp);

           // call max heapify on the reduced heap

           heapify(list, i, 0);

       }

   }

   // To heapify a subtree rooted with node i which is

   // an index in list[]. n is size of heap

   void heapify(ArrayList<Integer> list, int n, int i)

   {

       int largest = i; // Initialize largest as root

       int l = 2*i + 1; // left = 2*i + 1

       int r = 2*i + 2; // right = 2*i + 2

       // If left child is larger than root

       if (l < n && list.get(l) > list.get(largest))

           largest = l;

       // If right child is larger than largest so far

       if (r < n && list.get(r) > list.get(largest))

           largest = r;

       // If largest is not root

       if (largest != i)

       {

           int swap = list.get(i);

           list.set(i, list.get(largest));

           list.set(largest, swap);

           // Recursively heapify the affected sub-tree

           heapify(list, n, largest);

       }

   }

   /* A utility function to print list of size n */

   static void printlist(ArrayList<Integer> list)

   {

       int n = list.size();

       for (int i=0; i<n; ++i)

           System.out.print(list.get(i)+\" \");

       System.out.println();

   }

   // Driver program

   public static void main(String args[])

   {

       Scanner sc = new Scanner(System.in);

       // creating Arrayist

       ArrayList<Integer> list = new ArrayList<Integer>();

       System.out.print(\"How many elements you want to sort: \");

       int n = sc.nextInt();

      

       System.out.println(\"Enter \"+n+\" integers: \");

       for(int i=0; i<n; i++)

           list.add(sc.nextInt());

       HeapSort heap = new HeapSort();

heap.sort(list);

       System.out.println(\"Sorted list is\");

       printlist(list);

   }

}

/*

Sample run:

How many elements you want to sort: 8

Enter 8 integers:

2

7

1

18

20

4

3

11

Sorted list is

1 2 3 4 7 11 18 20

*/