Heapsort in Java

Below is an example of the Heapsort algorithm in Java. See the Heapsort page for more information and implementations.


heapsort in Java

public class HeapSort {
    public static void main(String[] args)
    {
        int[]    array  = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
        HeapSort sorter = new HeapSort();
        sorter.heapSort(array);
        System.out.println(java.util.Arrays.toString(array));
    }

    void heapSort(int[] array)
    {
        int size = array.length;

        // build heapSort (rearrange array)
        for (int i = size / 2 - 1; i >= 0; i--)
            heapify(array, size, i);

        // one by one extract an element from heapSort
        for (int i = size - 1; i >= 0; i--)
        {
            // move current root to end
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // call max heapify on the reduced heapSort
            heapify(array, i, 0);
        }
    }

    // to heapify a subtree rooted with node i which is an index in array[]
    static void heapify(int[] array, int size, int i)
    {
        int max   = i; // initialize max as root
        int left  = 2 * i + 1;
        int right = 2 * i + 2;

        // if left child is larger than root
        if (left < size && array[left] > array[max])
            max = left;

        // if right child is larger than max
        if (right < size && array[right] > array[max])
            max = right;

        // if max is not root
        if (max != i)
        {
            // swap
            int temp = array[i];
            array[i] = array[max];
            array[max] = temp;

            // recursively heapify the affected sub-tree
            heapify(array, size, max);
        }
    }
}

Discussion