堆排序 - Heap Sort
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆的特征
- 堆的数据结构近似完全二叉树，即每个节点存在两个子节点
- 当节点的值小于或等于父节点值，大于或等于子节点值称为大顶堆（也即根节点的值最大）
- 当节点的值大于或等于父节点值，小于或等于子节点值称为小顶堆（也即根节点的值最小）
- 若当前节点的索引为 k , 那么左子节点索引为 2k + 1, 右子节点索引为 2k + 2, 父节点索引为 (k - 1) / 2
在本文中我们以大顶堆为例
堆的动作 - 上浮
上浮 ： 是指在构建堆时，若节点的值大于父节点则将当前节点与父节点互相交换；直至该节点小于父节点时终止上浮（可以理解为一个新入职的员工能力出众晋升更高的职位）； 效果如下图
代码如下：
private void siftUp(int k) { // k == 0 时表明上浮到根节点，结束上浮操作 while (k > 0) { // 获取父节点索引 int parent = (k - 1) / 2; // 小于父节点时退出，结束上浮操作 if (less(parent, k)) { break; } // 与父节点交换数据 swap(parent, k); // 改变 k 的指向 继续上浮 k = parent; } }复制代码 堆的动作 - 下沉
下沉 ： 是指构建堆的过程中，若当前节点值小于子节点则将当前节点与子节点互相交换，直至该节点大于子节点时终止下沉（可以理解为一个leader能力平庸的时候被降职的过程，是不是有点很惨）； 效果如下图
代码如下：
private void siftDown (int k, int length) { // 获取左子节点索引 int childIndex = 2 * k + 1; // 判断是否存在子节点 while (childIndex < length) { // 判断左右子节点 查找最大的子节点 if (childIndex + 1 < length && !less(childIndex, childIndex + 1)) { childIndex++; } // 若当前节点大于子节点 退出循环 if (less(k, childIndex)) { break; } // 判断当前节点是否小于子节点, 若小于执行交换 swap(k, childIndex); // 改变 k 指向 k = childIndex; childIndex = 2 * k + 1; } }复制代码 堆排序
那么如何采用堆的数据结构，对一个无序的数组进行排序呢 ？
- 首先将无序数组构造成一个最大堆，此时根节点为最大值
- 将最后一个节点与根节点值交换，剔除最大值节点；
- 将剩下节点重新执行构造堆
- 循环执行第 2,3 两步操作
无序数组构造堆
将无序数组构造堆，可以采用上浮， 也可以采用下沉的方式处理
如上图所示，为采用上浮的方式构建堆，其流程是依次从下标为 0 开始对数组的每个元素进行上浮操作，直至最后得到一个有序的大顶堆。
如上图所示，为采用下沉的方式构建堆，其流程是依次从非叶子节点 开始对数组的每个元素进行下沉操作，直至最后得到一个有序的大顶堆。
代码如下：
for (int i = 0; i < array.length; i++) { // 上浮方式构建堆 siftUp(i); }复制代码 // 因为堆是完全二叉树的特性, 所以下标小于等于 array.length / 2 的节点为非叶子节点// 采用下沉的方式 从下往上构建子堆 for (int i = array.length / 2; i >= 0; i--) { siftDown(i, array.length); }复制代码 完成初始堆构造之后，剩下的工作就是重复进行以下逻辑(这个地方就不画图了)：
- 尾节点和根节点交换元素
- 剔除尾节点，对余下的元素进行子堆构造(构造堆的方式与初始堆一样)
完整代码如下 ：
public class HeapSort { private int[] array; public HeapSort(int[] array) { this.array = array; } private boolean less (int i, int j) { return array[i] > array[j]; } private void swap (int k, int j) { int temp = array[k]; array[k] = array[j]; array[j] = temp; } /** * 下沉操作 * * @param k */ private void siftDown(int k, int length) { // loop // 判断是否存在子节点 int childIndex = 2 * k + 1; while (childIndex < length) { // 查找最大的子节点 if (childIndex + 1 < length && !less(childIndex, childIndex + 1)) { childIndex++; } // 若当前节点大于子节点 退出循环 if (less(k, childIndex)) { break; } // 判断当前节点是否小于子节点, 若小于执行交换 swap(k, childIndex); // 改变 k 指向 k = childIndex; childIndex = 2 * k + 1; } } /** * 上浮操作 * * @param k */ private void siftUp(int k) { while (k > 0) { int parent = (k - 1) / 2; // 小于父节点时退出 if (less(parent, k)) { break; } // 与父节点交换数据 swap(parent, k); // 改变 k 的指向 k = parent; } } public void sort () { // 构造堆 for (int i = 0; i < array.length; i++) { siftUp(i); } print(); int n = array.length - 1; while (n > 0) { // 因为每次完成堆的构造后, 根节点为最大(小)值节点 // 将根节点与最后一个节点交换 swap(0, n); for (int i = 0; i <= n - 1; i++) { // 排除有序的节点 // 重新构造堆 siftUp(i); } print(); n--; } } private void sort1 () { // 构建堆 // 因为堆是完全二叉树的特性, 所以下标小于等于 array.length / 2 的节点为非叶子节点 // 采用下沉的方式 从下往上构建子堆 for (int i = array.length / 2; i >= 0; i--) { siftDown(i, array.length); } print(); int n = array.length - 1; while (n > 0) { // 因为每次完成堆的构造后, 根节点为最大(小)值节点 // 将根节点与最后一个节点交换 swap(0, n); for (int i = n / 2; i >= 0; i--) { // 排除有序的节点 // 重新构造堆 siftDown(i, n); } print(); n--; } } private void print () { for (Integer num : array) { System.out.print(num); System.out.print(","); } System.out.println(""); } public static void main(String[] args) { int[] array = { 10, 40, 38, 20, 9, 15, 25, 30, 32}; new HeapSort(array).sort(); System.out.println(""); new HeapSort(array).sort1(); }}复制代码 小结 ： 堆排序在哪里应用到了呢 ？ 可参考优先队列 PriorityQueue 的实现