Implement a method to sort a given array using the heap sort

Implement a method to sort a given array using the heap sort algorithm. Use the algorithm from the textbook (see below). You should finish implementing Build Max Heap and Max Heapify by the end of lab. You can finish implementing the full algorithm for homework. Build-Max-Heap(A, n) for i = [n/2] downto 1 Max-Heapify (A, i, n) Heapsort(A, n) Build-Max-Heap(A, n) for i = n downto 2 exchange A [1] with A[i] Max-Heapify(A, 1, i - 1) Max-Heapify(A, i, n) l = Left(i) r = Right(i) if l lessthanorequalto n and A[l] > A[i] largest = l else largest = i if r lessthanorequalto n and A[r] > A[largest] largest = r if largest notequalto I exchange A[i] with A[largest] Max-Heapify(A, largest, n) Write a driver program to test the Heapsort algorithm for the arrays of varying lengths provided in Canvas. Use the input files provided earlier.

Solution

Hi, Please find my implementation.

Please let me know in case of any issue.

public class HeapSort

{

   public void heapSort(int arr[])

   {

       int n = arr.length;

       BuildMaxHeap(arr, n);

       // One by one extract an element from heap

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

       {

           // Move current root to end

           int temp = arr[0];

           arr[0] = arr[i];

           arr[i] = temp;

           // call max heapify on the reduced heap

           MaxHeapify(arr, i, 0);

       }

   }

   void BuildMaxHeap(int arr[], int n){

       // Build heap (rearrange array)

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

           MaxHeapify(arr, n, i);

   }

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

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

   void MaxHeapify(int arr[], 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 && arr[l] > arr[largest])

           largest = l;

       // If right child is larger than largest so far

       if (r < n && arr[r] > arr[largest])

           largest = r;

       // If largest is not root

       if (largest != i)

       {

           int swap = arr[i];

           arr[i] = arr[largest];

           arr[largest] = swap;

           // Recursively heapify the affected sub-tree

           MaxHeapify(arr, n, largest);

       }

   }

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

   public static void display(int arr[])

   {

       int n = arr.length;

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

           System.out.print(arr[i]+\" \");

       System.out.println();

   }

   public static void main(String args[])

   {

       int arr[] = {12, 11, 13, 5, 6, 7};

       int n = arr.length;

       HeapSort ob = new HeapSort();

      

       System.out.println(\"Un-Sorted array is\");

       display(arr);

      

       ob.heapSort(arr);

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

       display(arr);

   }

}

/*

Sample run:

Un-Sorted array is

12 11 13 5 6 7

Sorted array is

5 6 7 11 12 13

*/