Implement Heapsort algorithm 75 run ut on 30 random numbers

Implement Heapsort algorithm 7.5 run ut on 30 random numbers. Show the initial heap after make heap and the heap after removing 5 elements

Please implement in Java. comments would be appreciated

EAPSORT Heap Data Structure struct heap key type SI 1.. nji S is indexed from 1 to n int heapsize heapsize only takes the values 0 through n void sift down (heap& H index i) To minimize the number of assignment of records index parent, la child the key initially at the key type sift key (sift ke y) is not assigned bool spot ound node until its final posi has been determined sift key parent spot fo und false spot found) if (2* parent H. he ap size && H. s12* parent] H. S. 2 parent larger child 2* parent Index of right child is 1. more than twice that of else larger child 2* paren parent. Index of left chi if (sift key H. SI larger child]) is twice that of parent H. S parent H. Sl larger child parent larger child else spot found true H. S parent sift key H) key type root (heap& key type key out key out Get key at the root H. SI1 H. SI heap size Move bottom key to root H. heapsize H. heap size Delete bottom node sift down (H, 1) Restore heap property return key out;

Solution

import java.util.Scanner;

/* Class HeapSort */
public class HeapSort
{
private static int N;
/* Sort Function */
public static void sort(int arr[])
{
heapify(arr);
for (int i = N; i > 0; i--)
{
swap(arr,0, i);
N = N-1;
maxheap(arr, 0);
}
}
/* Function to build a heap */
public static void heapify(int arr[])
{
N = arr.length-1;
for (int i = N/2; i >= 0; i--)
maxheap(arr, i);
}
/* Function to swap largest element in heap */
public static void maxheap(int arr[], int i)
{
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;

if (max != i)
{
swap(arr, i, max);
maxheap(arr, max);
}
}
/* Function to swap two numbers in an array */
public static void swap(int arr[], int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/* Main method */
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
int n, i;
/* Accept number of elements */
System.out.println(\"Enter number of integer elements\");
n = scan.nextInt();
/* Make array of n elements */
int arr[] = new int[ n ];
/* Accept elements */
/*Filling the array with random values*/
for (i = 0; i < n; i++){
arr[i] = (int)(Math.random() * 100);
}
/* Make array of n-5 elements */
int arr1[] = new int[ n-5 ];
/* Accept elements */
/*Filling the array with random values*/
for (i = 0; i < n-5; i++){
arr1[i] = arr[i];
}

/* Call method sort */
sort(arr);
sort(arr1);
/* Print sorted Array */
System.out.println(\"\ Elements after sorting \");
for (i = 0; i < n; i++)
System.out.print(arr[i]+\" \");
System.out.println();
System.out.println(\"\ Elements after sorting after removing 5 element \");
for (i = 0; i < n-5; i++)
System.out.print(arr1[i]+\" \");
System.out.println();
}
}