堆排序（英语：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]<nums[5]，即节点 2 小于其左子节点 5（其右子节点不存在），需要调整交换两者。如下图所示：
第二个非叶子节点 1：nums[1]<nums[3] 且 nums[1]<nums[4]，即节点 1 均小于其左右子节点，但其左子节点 3 更大，因此需要调整交换节点 1 与较大的子节点 3。如下图所示：
第三个非叶子节点 0：nums[0]<nums[1] 且 nums[0]<nums[2]，即节点 0 均小于其左右子节点，但其左子节点 1 更大，因此需要调整交换节点 0 与较大的子节点 1。如下图所示：
然而，调整完节点 0 与 节点 1 后我们发现原子树的堆序已被打破，此时 nums[1]<nums[4]，即节点 1 小于其右子节点 4，因此还需要继续对以节点 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]<arr[minIndex]){
minIndex = leftChild;
}
if(rightChild < size && arr[rightChild]<arr[minIndex]){
minIndex = rightChild;
}
if(minIndex!=index){
swap(arr,index,minIndex);
toMinHeap(arr,size,minIndex);
}
}
public void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}