Write a Java Program for HeapSort

Write a Java Program for HeapSort

Heap sort is a comparison-based sorting technique based on BinaryHeap data structure. It is similar to Selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.

public class HeapSort {
    public void sort(int arr[])
    {
        int n = arr.length;
 
        
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
 
        
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
 
            
            heapify(arr, i, 0);
        }
    }
 
    
    void heapify(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 (l < n && arr[l] > arr[largest])
            largest = l;
 
        
        if (r < n && arr[r] > arr[largest])
            largest = r;
 
       
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
 
            
            heapify(arr, n, largest);
        }
    }
 
    
    static void printArray(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();
        ob.sort(arr);
 
        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Output

Sorted array is 
5 6 7 11 12 13