Write a Java Program for HeapSort

Write a Java Program for HeapSort

Table of Contents

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.

Write a Java Program for HeapSort
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 

Leave a Comment

Your email address will not be published. Required fields are marked *