package algo;

import java.util.Arrays;

public class Heap {
    public static void main(String[] args) {
        Heap.sort(new int[] { 2, 4, 3, 5, 1, 6 });
    }

    public static void sort(int[] nums) {
        for (var i = nums.length / 2 - 1; i >= 0; i--) {
            heapify(nums, i, nums.length);
        }
        for (var i = nums.length - 1; i >= 0; i--) {
            var t = nums[i];
            nums[i] = nums[0];
            nums[0] = t;
            heapify(nums, 0, i);
        }
        System.out.println(Arrays.toString(nums));
    }
    
    public static void heapify(int[] nums, int root, int len) {
        var child = root * 2 + 1;
        if (root < len && child < len) {
            if (child + 1 < len && nums[child] < nums[child + 1])
                child++;
            if (nums[root] < nums[child]) {
                var t = nums[root];
                nums[root] = nums[child];
                nums[child] = t;
                heapify(nums, child, len);
            }
        }
    }
}