HeapSort.java

public class HeapSort {

    public static void heapSort(int[] arr) {
        final int length = arr.length;
        final Heap heap = new Heap(length);
        for  (int element : arr) {
            heap.insertHeap(element);
        }

        for (int i = length - 1; i >= 0; --i) {
            arr[i] = heap.deleteHeap();
        }
    }

    private static class Heap {
        private int heapSize;
        private final int[] items;

        private Heap(int count) {
            heapSize = 0;
            items = new int[count + 1];
        }

        private void insertHeap(int item) {
            int i = ++heapSize;
            while (i != 1 && item > items[i / 2]) {
                items[i] = items[i / 2];
                i /= 2;
            }

            items[i] = item;
        }

        private int deleteHeap() {
            int item = items[1];
            int temp = items[heapSize--];
            int parent = 1;
            int child = 2;

            while (child <= heapSize) {
                if (child < heapSize && items[child] < items[child + 1]) {
                    child++;
                }

                if (temp >= items[child]) {
                    break;
                }

                items[parent] = items[child];
                parent = child;
                child *= 2;
            }

            items[parent] = temp;
            return item;
        }
    }

}