堆排序（Heap Sort）实现

堆排序（英语：Heapsort）是指利用堆（heap）这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

堆可看作是一个「完全二叉树」的结构：

记一个二叉树的深度为 h，若除第 h 层外，该二叉树的其它各层[1, h−1] 的节点数均达到最大值（满的），且第 h 层所有的节点均连续集中在最左边，那么这棵树即为一棵 完全二叉树。

根据父子节点之间的关系，堆又可大致分为两类（如下图所示）：

大根堆／大顶堆：每个节点的值均大于等于其左右孩子节点的值；
小根堆／小顶堆：每个节点的值均小于等于其左右孩子节点的值。
若对堆中的节点按照层序遍历的方式进行编号，则可将其结构映射到数组中。若从 0 开始编号（如上图所示），则节点 i 的「左子节点」为2i+1，「右子节点」为2i+2，其父节点是 (i-1)/2 (注意： 0节点除外)

此时大根堆和小根堆满足以下关系：
大根堆：nums[i] >= nums[2i+1]  &  nums[i] >= nums[2i+2]
小根堆：nums[i] <= nums[2i+1]  &  nums[i] <= nums[2i+2]

同样地，若从 1 开始对堆中的节点进行编号，则节点 i的「左子节点」为2i，「右子节点」为 2i+1，此时大根堆和小根堆满足以下关系：
大根堆：nums[i] >= nums[2i]  &  nums[i] >= nums[2i+1]
小根堆：nums[i] <= nums[2i]  &  nums[i] <= nums[2i+1]

堆与排序：

对于一个待排序的包含 n个元素的数组nums，堆排序 通常包含以下几个基本步骤：

建堆：将待排序的数组初始化为大根堆（小根堆）。此时，堆顶的元素（即根节点）即为整个数组中的最大值（最小值）。
交换和调整：将堆顶元素与末尾元素进行交换，此时末尾即为最大值（最小值）。除去末尾元素后，将其他 n−1 个元素重新构造成一个大根堆（小根堆），如此便可得到原数组 n 个元素中的次大值（次小值）。
重复步骤二，直至堆中仅剩一个元素，如此便可得到一个有序序列了。
通过以上步骤我们也可以发现：

对于「升序排列」数组，需用到大根堆；
对于「降序排列」数组，则需用到小根堆。

假设有一个待排序的数组 nums=[5, 2,1, 9, 6, 8]，我们可将其构造成一个二叉树，如下图所示：

下面以 nums=[5,2,1,9,6,8] 为例，讲解下如何构造大根堆，并实现其「升序排列」。

I. 构造大根堆
如何将一个完全二叉树构造成一个大顶堆？

一个很好的实现方式是从最后一个「非叶子节点」为根节点的子树出发，从右往左、从下往上进行调整操作。

需要注意的是：

        若完全二叉树从 0 开始进行编号，则第一个非叶子节点为（n-2）/2；若完全二叉树从 1 开始进行编号，则第一个非叶子节点为 n/2。
        调整针对的是以该非叶子节点为根节点的子树，即对该根节点以下的所有部分均进行调整操作。由于我们是从右往左、从下往上遍历非叶子节点的，因此当遍历到某个非叶子节点时，它的子树（不包括该节点本身）已经是堆有序的。

对于以某个非叶子节点的子树而言，其基本的调整操作包括:

1.如果该节点大于等于其左右两个子节点，则无需再对该节点进行调整，因为它的子树已经是堆有序的；
2.如果该节点小于其左右两个子节点中的较大者，则将该节点与子节点中的较大者进行交换，并从刚刚较大者的位置出发继续进行调整操作，直至堆有序。

对于nums=[5,2,1,9,6,8]，其包含n=length(nums)=6 个元素，第一个非叶子节点为(n-2)/2=2，对应的基本建堆（大根堆）步骤如下：

第一个非叶子节点 2：nums[2]

第二个非叶子节点 1：nums[1]

第三个非叶子节点 0：nums[0]

然而，调整完节点 0 与 节点 1 后我们发现原子树的堆序已被打破，此时 nums[1]

至此，全部的调整完毕，我们也就建立起了一个大根堆 nums=[9,6,8,2,5,1]：

II. 排序
建立起一个大根堆后，便可以对数组中的元素进行排序了。总结来看，将堆顶元素与末尾元素进行交换，此时末尾即为最大值。除去末尾元素后，将其他n−1 个元素重新构造成一个大根堆，继续将堆顶元素与末尾元素进行交换，如此便可得到原数组 n 个元素中的次大值。如此反复进行交换、重建、交换、重建，便可得到一个「升序排列」的数组。

对于大根堆 nums=[9, 6, 8, 2, 5, 1]，其堆排序基本步骤如下：

1.最大元素：此时堆顶元素为最大值，将其交换到末尾，如下所示：

交换完成后，除去末尾最大元素，此时需要对堆进行重建，使得剩余元素继续满足大根堆的要求。如下所示：

2.次大元素：此时堆顶元素为待排序元素中的最大值（即原数组中的次大值），将堆顶元素交换到末尾，如下所示：

交换完成后，除去末尾最大元素，此时需要对堆进行重建，使得剩余元素继续满足大根堆的要求（省略）。

3.第三大元素：此时堆顶元素为待排序元素中的最大值（即原数组中的第三大值），将堆顶元素交换到末尾，如下所示：

交换完成后，除去末尾最大元素，此时需要对堆进行重建，使得剩余元素继续满足大根堆的要求（省略）。

4.第四大元素：此时堆顶元素为待排序元素中的最大值（即原数组中的第四大值），将堆顶元素交换到末尾，如下所示：

交换完成后，除去末尾最大元素，此时需要对堆进行重建，使得剩余元素继续满足大根堆的要求（省略）。

5.次小元素（第五大元素）：此时堆顶元素为待排序元素中的最大值（即原数组中的次小元素或第五大元素），将堆顶元素交换到末尾，如下所示：

交换完成后，除去末尾最大元素，此时堆中仅剩一个元素，即为原数组中的最小值。

至此，基于大根堆的升序排列完成，如下所示：

本题分析：

注意到，在每一次建好大根堆后，堆顶元素即为当前范围内的最大值，因此要得到数组中的第 K 个最大元素需要：建堆（大根堆） K 次，此时堆顶元素即为第 K 个最大元素。

public class HeapSort {
    @Test
    public void test() {
        int[] arr = {5, 2, 1, 9, 6, 8};
        heapSort(arr);
    }

    public void heapSort(int[] arr) {
        //从第一个非叶子节点进行调整
        int startIndex = (arr.length - 2) / 2;
        for (int i = startIndex; i >= 0; i--) {
            toMaxHeap(arr, arr.length, i);
        }
        //已经变成大根堆，交换堆顶和最后一个元素，循环
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, i, 0);
            //size=i,一直在减小
            toMaxHeap(arr, i, 0);
        }
        System.out.println(Arrays.toString(arr));
    }

    //构造大根堆
    public void toMaxHeap(int[] arr, int size, int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int maxIndex = index;
        //找到最大的元素
        if (leftChildIndex < size && arr[leftChildIndex] > arr[maxIndex]) {
            maxIndex = leftChildIndex;
        }
        if (rightChildIndex < size && arr[rightChildIndex] > arr[maxIndex]) {
            maxIndex = rightChildIndex;
        }
        //如果是子节点比父节点大，则进行交换
        if (maxIndex != index) {
            swap(arr, index, maxIndex);
        //重新调整大根堆顺序
            toMaxHeap(arr, size, maxIndex);
        }
    }

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

//可以直接用 PriorityQueue 优先队列实现
public class findKthLargest {
    @Test
    public void test(){
        int[] arr = {56,275,12,6,45,478,41,1236,456,12,546,45};
        int[] largest = KthLargest(arr, 5);
        System.out.println(Arrays.toString(largest));
    }


    public int[] KthLargest(int[] arr,int k){
        //1.取前k个元素先组成topk数组
        int[] topK = new int[k];
        for (int i = 0; i < k; i++) {
            topK[i] = arr[i];
        }
        //2.构造小根堆,从第一个非叶子节点进行调整
        int startIndex = (k - 2) / 2;
        for (int i = startIndex; i >= 0; i--) {
            toMinHeap(topK, k, i);
        }

        //3.从k开始遍历数组，比较大小，是否替换元素
        //小根堆第一个元素最小，替换掉最小的
        for (int i = k - 1; i < arr.length; i++) {
            if(arr[i] > topK[0]){
                topK[0] = arr[i];
                // 重新调整结构为小根堆
                toMinHeap(topK, k, 0);
            }
        }
        return topK;
    }

    public void toMinHeap(int[] arr,int size,int index){
        int leftChild = index * 2 + 1;
        int rightChild = index * 2 + 2;
        int minIndex = index;
        if(leftChild < size && arr[leftChild]