import java.util.Arrays;

/**
 * Description: 堆排序
 * Date: 2020-12-26
 * Time: 6:13 PM
 */
public class HeapSort {

    int len;

    void buildMaxHeap(int[] arr) {   // 建立大顶堆
        len = arr.length;
        for (int i = len / 2; i >= 0; i--) {
            heapify(arr, i);
        }
    }

    void heapify(int[] arr, int i) {     // 堆调整
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest);
        }
    }

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

    int[] heapSort(int[] arr) {
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0);
        }
        return arr;
    }

    public static void main(String[] args) {

        System.out.println(Arrays.toString(new HeapSort().heapSort(new int[]{1,4,3,7,2,10,5,21,6})));

    }
}