import java.util.Arrays;
import java.util.Random;

public class HeadSort {
    
    public static void main(String[] args) {
        //测试代码
        int[] arr = new int[20];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt() % 1000;
        }
        System.out.println(Arrays.toString(arr));
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] heapSort(int[] arr) {

        // 构建最大堆
        buildHead(arr);

        // 每次将堆顶节点移到数组尾部，调整堆大小
        for (int i = 0; i < arr.length; i++) {

            // 即将要被堆删除的节点序号
            int last = arr.length - i - 1;

            swap(arr, 0, last);

            // 改变传递的len参数表示堆将节点删除
            heapify1(arr, 0, last);
        }
        return arr;
    }
    
    public static void buildHead(int[] arr) {
        int len = arr.length;
        //在满二叉树中，叶子节点数量是非叶子节点的2倍+1
        //第n-1层的最后一个节点就是len/2
        for (int i = len / 2; i >= 0; i--) {
            heapify1(arr, i, len);
        }
    }
    
    //递归下沉方式
    public static void heapify1(int[] arr, int parentIndex, int len) {
        // 左右孩子节点
        int left = 2 * parentIndex + 1;
        int right = 2 * parentIndex + 2;
        // 该父节点没有左孩子
        if (left >= len) {
            return;
        }
        int latest = left;
        /*
        将节点进行下沉，如果进行了交换，还得继续下沉，一直到成为叶子节点
         */
        // 得出左右孩子中的最大值
        if (right < len && arr[right] > arr[left]) {
            latest = right;
        }
        if (arr[latest] > arr[parentIndex]) {
            swap(arr, parentIndex, latest);
            heapify1(arr, latest, len);
        }
    }

    //循环下沉方式
    public static void heapify2(int[] arr, int parentIndex, int len) {

        //先将父节点值保存下来，跟左右的孩子比较，如果大于，跳出循环，如果小于，进行交换
        //交换之后节点继续下沉，一直到成为叶子节点
        int tmp = arr[parentIndex];
        int children = 2 * parentIndex + 1;
        while (children < len) {

            // 左孩子大于右孩子，用左孩子的值与父节点比较
            if (children + 1 < len && arr[children + 1] > arr[children]) {
                children++;
            }

            /*
            父节点大于孩子的值，不用交换
            使用的是tmp，而不是arr[parentIndex]，因为一直是单向赋值，没有交换
            直到确认tmp属于哪个节点，在循环外面将tmp赋值
             */
            if (tmp >= arr[children]) {
                break;
            }

            // 将孩子节点的值赋给父节点，孩子节点暂时不变
            arr[parentIndex] = arr[children];
            parentIndex = children;
            children = children * 2 + 1;

        }
        arr[parentIndex] = tmp;
    }

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