Heap Sort

class Solution {

    /*Solution 1*/
    public void sort(int arr[])
    {
        int n = arr.length;
 
        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
 
        // One by one extract an element from heap
        for (int i = n - 1; i >= 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
 
            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }
 
    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    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 left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;
 
        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;
 
        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
 
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    /*Solution 2*/
    public void heapSort(int[] nums) {
        int tmp = 0;
        for (int i=0; i<nums.length; i++) {
            nums = heapify(nums, i);
        }

        for (int i=nums.length-1; i>=0; i--) {
            tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            nums = topHeapify(nums, i + 1);
        }
    }

    public int[] heapify(int[] nums, int index) {
        int prev = index, current = (index + 1) / 2 - 1;
        int tmp = 0;
        while (current >= 0 && nums[current] < nums[prev]) {
            tmp = nums[current];
            nums[current] = nums[prev];
            nums[prev] = tmp;
            prev = current;
            current = (current + 1) / 2 - 1;
        }
        return nums;
    }

    public int[] topHeapify(int[] nums, int limit) {
        int prev = 0, left = 1, right = 2;
        int tmp = 0, sw = left;
        while ((left < limit && nums[prev] < nums[left]) || 
            (right < limit && nums[prev] < nums[right])) {
            if (left < limit && right < limit) {
                sw = nums[left] > nums[right] ? left : right;
            }else if (left < limit && nums[prev] < nums[left]) {
                sw = left;
            }else{
                sw = right;
            }
            tmp = nums[sw];
            nums[sw] = nums[prev];
            nums[prev] = tmp;
            prev = sw;
            left = (sw + 1) * 2 - 1;
            right = (sw + 1) * 2;
        }
        return nums;
    }
}