Heap sort

A Heap is an almost complete binary tree.In this tree, if the maximum level is i, then, upto the (i-1)th level should be complete. At level i, the number of nodes can be less than or equal to 2^i. If the number of nodes is less than 2^i, then the nodes in that level should be completely filled, only from left to right.

The property of an ascending heap is that, the root is the lowest and given any other node i, that node should be less than its left child and its right child. In a descending heap, the root should be the highest and given any other node i, that node should be greater than its left child and right child.

To sort the elements, one should create the heap first. Once the heap is created, the root has the highest value. Now we need to sort the elements in ascending order. The root can not be exchanged with the nth element so that the item in the nth position is sorted. Now, sort the remaining (n-1) elements. This can be achieved by reconstructing the heap for (n-1) elements.

Following is the java code which sorts an array in ascending order using Heap Sort:
(Time Complexity of the algorithm is - O(nlogn))

public class HeapSort {

    private static int getLeft(int i){
        return 2*i+1;
    }

    private static int getRight(int i){
        return 2*i+2;
    }

    private static void buildHeap(int[] arr){
        for(int i=(arr.length-2)/2; i>=0; i--){
           heapify(arr, arr.length, i);
        }
    }

    private static void heapify(int[] arr, int heapSize, int k){
        int leftChild = -1;
        if(k >= heapSize){
            return;
        }
        if(getLeft(k) < heapSize){
            leftChild = arr[getLeft(k)];
        }

        int rightChild = -1;
        if(getRight(k) < heapSize){
            rightChild = arr[getRight(k)];
        }

        if(arr[k] > leftChild && arr[k] > rightChild){
            return;
        }

        if(leftChild < rightChild){
            swap(arr, k, getRight(k));
            heapify(arr, heapSize, getRight(k));
        }else {
            swap(arr, k, getLeft(k));
            heapify(arr, heapSize, getLeft(k));
        }

    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int x[] = new int[]{9,3,1,10,15,16,8,7,4,5,89};
        buildHeap(x);
        int heapSize = x.length;
        for(int i = x.length-1; i>=0; i--){
            swap(x, 0, heapSize-1);
            --heapSize;
            heapify(x, heapSize, 0);
        }

        System.out.println(Arrays.toString(x));
    }
}