排序--堆排序
版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/ad3082312012
概念
堆： 堆是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子（如果存在的话）的值，称为最大堆；或者每个节点的值都小于或等于其左右孩子（如果存在的话）的值，称为最小堆。
完全二叉树：
complete binary tree
最大堆：
max heap
最小堆：
min heap
图片来源: 常见排序算法 - 堆排序 (Heap Sort)
堆排序：利用堆（这里使用最大堆）进行排序的方法。其基本思想是：将待排序的序列构造成一个最大堆，此时待排序序列的最大值就是堆顶的根节点，将其移走（其实就是将其与待排序序列的最后一个元素进行交换，此时待排序序列最后一个元素就是最大值），然后将剩余的序列重新构造成一个堆，如此反复，直到待排序序列只有一个元素为止，则排序完成。
性质
已知arr[0...n-1]是长度为n的最大堆数组，下标从0开始，那么对于下标为i的节点I，有：
(1). 如果I的左孩子存在的话，那么I的左孩子节点的下标为 left(i) = 2*i+1；
(2). 如果I的右孩子存在的话，那么I的右孩子节点的下标为 right(i) = 2*i+2;
(3). 如果I双亲节点存在的话，那么I的双亲节点的下标为 parent(i) = (i-1)/2; (向下取整)
基本操作
- 构建最大堆 buildMaxHeap(int[] arr)：将待排序序列arr构建成最大堆；
- 调整最大堆 adjustHeap(int arr[], int begin, int end): 已知arr[begin]的左子树和右子树都满足最大堆，那么调节节点arr[begin]，将以arr[begin]为根节点的二叉树调整为最大堆。
对于堆排序，最重要的就是构建最大堆和调整最大堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
Java实现
// 定义接口
interface Sorter {
/**
* 将数组按升序排序
*/
int[] sort(int[] arr);
/**
* 交换数组arr中的第i个位置和第j个位置的关键字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 堆排序
class HeapSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
heapSort(arr);
return arr;
}
private void heapSort(int[] arr) {
buildMaxHeap(arr); // 构建最大堆
// 将最大堆堆顶元素与数组末尾元素交换，并将前n-1序列重新构造成最大堆,重复n-1次
for (int i = arr.length - 1; i >= 1; i--) {
swap(arr, 0, i); // 将堆顶元素和当前未经排序的子序列的最后一个元素进行交换
adjustHeap(arr, 0, i - 1); // 将arr[0...i-1](前i个元素)重新调整为最大堆
}
}
/**
* 将指定数组arr构建成最大堆
*/
private void buildMaxHeap(int[] arr) {
int len = arr.length;
// 从最后一个非叶子节点往前遍历，将当前序列构成最大堆
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, len - 1);
}
}
/**
* 假定arr[begin]的左子树和右子树均满足最大堆，那么调节节点arr[begin]，将以arr[begin]为根节点的二叉树调整为最大堆。
*/
private void adjustHeap(int[] arr, int begin, int end) {
int tmp = arr[begin];
int j;
for (j = 2 * begin + 1; j <= end; j = 2 * j + 1) {
// j=2*begin+1表示j对应二叉树节点的左孩子
if (j + 1 <= end && arr[j] < arr[j + 1]) {
// 如果当前节点的右孩子存在且左孩子的值小于右孩子
j++; // j为左右孩子较大记录的下标
}
if (tmp >= arr[j]) // tmp的值已经大于arr[j]，则调整完毕，跳出循环
break;
arr[begin] = arr[j]; // 当前根节点并未均大于左右节点(如果有的话)，重新给当前根节点赋值
begin = j; // begin指向新的可能需要进行最大堆调整的子树的根节点
}
arr[begin] = tmp;
}
}
堆排序其实也是一种选择排序，是一种树形选择排序。在简单选择排序中，从arr[0...n-1]中选择最小（或最大）记录，需要比较n-1次，然后再从剩下arr[1...n-1]的n-1个元素中选择最小（或最大）记录，需要比较n-2次。然而事实上这n-2次比较中，有许多已经在前一趟n-1次的比较中做过了；而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数，提高算法效率。
复杂度
时间复杂度：
对于n个关键字序列，每个节点需比较log2(n)次，因此其时间复杂度为O(nlogn)。
由于堆排序对原始记录的排序状态并不敏感，所以它的最好、最坏、平均时间复杂度均为O(nlogn)
由于初始构建堆所需要的比较次数较多，所以堆排序不适合待排序序列个数少的情况。
空间复杂度：
最好情况=平均情况=最坏情况=O(1)
