以前一直听到堆排序这个词，只知道其排序效率很高，可以达到O(nlogn)的时间复杂度，最坏情况也是如此（这点与快速排序不同，快排最坏情况下为O(n2)）。但对其一直保持着一种敬畏的态度，没有去深究他，今天蹦着学习的态度，参考图书馆的书，并用代码实现，在这里对其进行一番总结。
堆(heap)
一开始听到堆这个词，以为是动态内存分配里面的内存区“堆”，但今天才发现其实这两者完全没有关系。 这里的堆是一个表(list)，记为array，并满足：
为什么有这样的定义呢，其实这与完全二叉树有关。
如上图，当左边的完全二叉树按照红色的序号存储到一个数组中，就是一个堆。不难发现，在该树中，标号为k的节点的左子节点标号为2k 1，右子节点为2k 2，所以其实堆其实就是指其所对应的逻辑结构——完全二叉树——的任一父节点都大于等于其子节点。这样的堆叫大根堆（或大顶堆），类似地，右边的堆叫小根堆，其任一父节点都小于等于其子节点。我们这里只讨论大根堆，搞定了大根堆，小根堆其实也是差不多的。
堆排序
堆排序就是基于堆这一数据结构的一种排序方法，属于选择排序的一种。
堆排序有以下几个步骤： (1) 将待排序的序列构建成一个堆 (2) 此时堆顶一定是最大的数，将其与序列的未排序部分的最后一个值交换位置（序列分成两部分，前半部分是未排序的，后半部分是排好序的） (3) 此时树根的值可能不符合堆的定义，需要将其调整为堆，方法是不断与较大的子节点交换位置，直到满足定义位置 (4) 重复(2)(3)直到排好序为止
例子图解点这里
代码实现
代码语言：javascript复制public static void heapSort(int[] arr) {
int lastUnsorted; // 记录最后一个未排序的位置
buildHeap(arr);
for (lastUnsorted = arr.length - 1; lastUnsorted > 0; lastUnsorted--) {
// 交换最后一个未排序的值与堆顶的值
int temp = arr[lastUnsorted];
arr[lastUnsorted] = arr[0];
arr[0] = temp;
heapAdjust(arr, 0, lastUnsorted - 1);
}
}
/*
* 建立大根堆
*/
public static void buildHeap(int[] arr) {
// 从最后一个非叶子节点开始，将其与其子树调整成大根堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapAdjust(arr, i, arr.length - 1);
}
}
/*
* arr[low 1...high]满足大根堆的定义
* 调整arr使arr[low...high]成为大根堆
*/
public static void heapAdjust(int[] arr, int low, int high) {
int temp = arr[low];
// 使用i记录左右子节点较大值的下标
for(int i = 2 * low 1; i <= high; i = i * 2 1) {
if (i < high && arr[i] < arr[i 1]) { // 若右子节点更大，则i
i ;
}
if (temp >= arr[i]) { // 完成
break;
} else {
arr[low] = arr[i];
low = i;
}
}
arr[low] = temp;
}无注释简短版
代码语言：javascript复制public class HeapSort {
public static void main(String[] args) {
int arr[] = {6, 5, 3, 1, 8, 7, 9, 0, 6, 5, 3, 1, 8, 7, 10, 20};
for(int i = arr.length / 2 - 1; i >= 0; i--) {
heapAdjust(arr, i, arr.length - 1);
}
for(int i = arr.length - 1; i > 0; i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
heapAdjust(arr, 0, i - 1);
}
for (int i = 0; i < arr.length; i ) {
System.out.print(arr[i] ",");
}
}
public static void heapAdjust(int[] arr, int low, int high) {
int temp = arr[low];
for(int i = low * 2 1; i <= high; i = i * 2 1) {
if(i < high && arr[i 1] > arr[i]) {
i ;
}
if(temp > arr[i]) break;
arr[low] = arr[i];
low = i;
}
arr[low] = temp;
}
}补充
构建一个堆： 从最后一个非叶子节点，从右往左，从下往上，调整，使得以该节点作为根节点的子树满足堆的定义。 向堆插入数据： 插入到最后一个位置，然后往上面调整。 删除堆顶元素： 将堆的最后一个元素放到堆顶，并往下调整。
