Jacob_Thomas

heapsort

Jan 28th, 2021
664
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. class HeapSort{
  3.     public static void main(String args[]){
  4.         Scanner sc = new Scanner(System.in);
  5.         System.out.println("Enter the array size");
  6.         int n = sc.nextInt();
  7.         int arr[] = new int[n];
  8.         for(int x = 0; x < n; x++){
  9.             arr[x] = sc.nextInt();
  10.         }
  11.         for (int x = n / 2 - 1; x >= 0; x--){
  12.             HeapSort.heapify(arr, n, x);
  13.         }
  14.         for (int x = n - 1; x > 0; x--){
  15.             int temp = arr[0];
  16.             arr[0] = arr[x];
  17.             arr[x] = temp;
  18.             HeapSort.heapify(arr, x, 0);
  19.         }
  20.         System.out.println(Arrays.toString(arr));
  21.        
  22.     }
  23.     public static void heapify(int arr[], int n, int i){
  24.         int largest = i;
  25.         int l = 2 * i + 1;
  26.         int r = 2 * i + 2;
  27.        
  28.         if(l < n && arr[l] > arr[largest]){
  29.             largest = l;
  30.         }
  31.         if(r < n && arr[r] > arr[largest]){
  32.             largest = r;
  33.         }
  34.         if(largest != i){
  35.             int temp = arr[i];
  36.             arr[i] = arr[largest];
  37.             arr[largest] = temp;        
  38.             heapify(arr, n, largest);
  39.         }
  40.  
  41.     }
  42. }
RAW Paste Data