Java Program for Heap Sort

 Java Program for Heap Sort

import java.util.*;

public class Heapdemo
{

    int left(int i) {
        return 2 * i + 1;
    }

    int right(int i) {
        return 2 * i + 2;
    }

    void minheapify(int arr[], int n, int i) {
        int l, r, smallest, temp;
        l = left(i);
        r = right(i);
        if (l < n && arr[l] < arr[i]) {
            smallest = l;
        } else {
            smallest = i;
        }
        if (r < n && arr[r] < arr[smallest]) {
            smallest = r;
        }

        if (smallest != i) {
            temp = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = temp;
            minheapify(arr, n, smallest);
        }
    }

    void heapSort(int arr[], int n) {
        int i, temp;

        for (i = n / 2 - 1; i >= 0; i--) {
            minheapify(arr, n, i);
        }

        for (i = n - 1; i >= 0; i--) {
            temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            minheapify(arr, i, 0);
        }
    }

    public static void main(String[] args) {
        Heapdemo h = new Heapdemo();
        int arr[] = new int[20];
        int i = 0, n;
        Scanner s = new Scanner(System.in);

        System.out.println("Enter the size of array : ");
        n = s.nextInt();
        System.out.println("\nEnter the elements : ");
        for (i = 0; i < n; i++) {
            arr[i] = s.nextInt();
        }

        for (i = (n - 1) / 2; i >= 0; i--) {
            h.minheapify(arr, n, i);
        }

        System.out.println("\nArray after Minheap \n");

        for (i = 0; i < n; i++) {
            System.out.println(arr[i]);
        }

        h.heapSort(arr, n);

        System.out.println("\nArray after Heap sort \n");

        for (i = n - 1; i >= 0; i--) {
            System.out.println(arr[i]);
        }

    }

}

Output:

run:
Enter the size of array :
7

Enter the elements :
48
0
-1
82
10
2
100

Array after Minheap

-1
0
2
82
10
48
100

Array after Heap sort

-1
0
2
10
48
82
100