转载：算法：堆排序HeapSort
转载：算法：堆排序HeapSort
原文链接：https://zhuanlan.zhihu.com/p/104110241
动画 | 什么是堆排序？
公众号『算法无遗策』
回顾一下我们学过的选择排序，在无序区找到一个最小（大）的元素需要比较n-1次，找到第二小的元素需要比较n-2次，直到最后比较1次。而堆排序因为二叉堆的性质，堆顶就是最大的元素，查找次数只有一次，但是将无序转成有序中间还需要一个预处理过程：构造堆有序。
堆有序并不代表数组有序，堆有序是满足二叉堆性质的：
1.父节点的键值总是优先于任何一个子节点的键值；
2.左右子树都是一个二叉堆。
所以堆排序分为两个阶段，构造堆有序和下沉排序阶段。
构造堆有序阶段是将原始数据重新组织安排到一个二叉堆中，堆有序就是一棵二叉树的每个节点都优先于它的两个子节点，不代表数组有序；
下沉排序阶段是将二叉堆中取出优先级高的直至取出所有元素，得到数组有序结果。
构造堆有序的方式有两种，一种是上浮，另一种是下沉。这里以最大堆为例。
自低向上的堆有序化（上浮）
上浮是某节点与其父节点的比较，如果某节点比其父节点要大，就通过交换的方式进行修复堆。如果这个节点仍然比现在的父节点还大，可以通过循环的方式进行修复堆，直到遇到更大的父节点。
那从哪个节点开始呢？
如果从数组最后一个节点进行开始上浮操作，它的父节点和祖父节点大小关系是不确定的，如果它的祖父节点比它父节点小，并不能保证整个完全二叉树能够二叉堆化。
所以从根节点的左孩子开始进行，数组下标为1开始，进行自底向上的堆有序化。在循环进行比较的时候会发现，这个节点已经进行过修复堆了，所以当上浮操作不再交换的时候可以做一个标记，截止进行比较。
如果能够合理优化的话，在时间上的消耗有可能要比下沉阶段的还要少。
动画
算法动画视频 地址 https://www.bilibili.com/video/av79323423/?p=1
[高清 720P] 堆排序_P1_堆有序 上浮 [最优化的质量和大小].flv
Code
package cn.study.sort;
import java.util.Arrays;
public class HeapSort1 {
//堆有序化：自底向上
public static void buildHeap(int[] array) {
//从数组第2个元素开始
for (int i = 1; i < array.length; i++) {
siftUp(array, i);
}
}
//上浮：和添加元素的上浮不同，减少计算次数
public static void siftUp(int[] array, int i) {
int flag = i;
for(; i > 0 && array[i] > array[parent(i)]; i = parent(i)){
if(flag != i){break;}
flag = parent(i);
swap(array, i, parent(i));
System.out.println("交换：" + Arrays.toString(array));
}
}
public static void swap(int[] array, int i, int j) {
if(i == j){return;}
//按位异或运算符"^"的运算规律是：两个操作数(二进制形式)的位中，相同则结果为0，不同则结果为1。
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
public static int parent(int i) {
return (i - 1) / 2;
}
public static void main(String[] args) {
int[] array = {13,9,15,11,3,7,17,5,1};
System.out.println("初始状态：" + Arrays.toString(array));
buildHeap(array);
System.out.println(Arrays.toString(array)); //[17, 11, 15, 9, 3, 7, 13, 5, 1]
}
}
Result
初始状态 [13, 9, 15, 11, 3, 7, 17, 5, 1]
交换 [15, 9, 13, 11, 3, 7, 17, 5, 1]
交换 [15, 11, 13, 9, 3, 7, 17, 5, 1]
交换 [15, 11, 17, 9, 3, 7, 13, 5, 1]
交换 [17, 11, 15, 9, 3, 7, 13, 5, 1]
[17, 11, 15, 9, 3, 7, 13, 5, 1]
自顶向下的堆有序化（下沉）
下沉是当前节点和左右孩子三者之中的比较，在整个进行自顶向下堆有序化的过程中，它是从非叶子节点开始的，即数组最后一个节点的父节点。
动画
算法动画视频 地址 https://www.bilibili.com/video/av79323423/?p=2
[高清 720P] 堆排序_P2_堆有序 下沉 [最优化的质量和大小].flv
Code
package cn.study.sort;
import java.util.Arrays;
public class HeapSort1 {
//堆有序化：自底向上
public static void buildHeap(int[] array) {
//从数组第2个元素开始
for (int i = 1; i < array.length; i++) {
siftUp(array, i);
}
}
//堆有序化：自顶向下
public static void buildHeap2(int[] array) {
for(int i = parent(array.length - 1); i >= 0; i--){
siftDown(array, i);
}
}
//上浮：和添加元素的上浮不同，减少计算次数
public static void siftUp(int[] array, int i) {
int flag = i;
for(; i > 0 && array[i] > array[parent(i)]; i = parent(i)){
if(flag != i){break;}
flag = parent(i);
swap(array, i, parent(i));
System.out.println("交换：" + Arrays.toString(array));
}
}
//下沉
//i为当前节点，是它的左孩子和右孩子的父节点
//在左孩子和右孩子中找到元素值最大的一个，然后与父节点交换元素值。
public static void siftDown(int[] array, int i) {
while(leftChild(i) < array.length){
int l = leftChild(i);
if(l + 1 < array.length && array[l] < array[l + 1]){//如果有右孩子，并且右孩子元素的值比左孩子元素的值大
l++;//记录右孩子的索引值
}
if(array[l] < array[i]){//如果子节点的元素值比父节点小，就不用交换元素值
break;
}
swap(array, l, i);//将子节点的元素值与父节点的元素值交换
System.out.println("交换：" + Arrays.toString(array));
i = l;//记录被调整的子节点的索引
}//end of while
}
public static void swap(int[] array, int i, int j) {
if(i == j){return;}
//按位异或运算符"^"的运算规律是：两个操作数(二进制形式)的位中，相同则结果为0，不同则结果为1。
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
public static int parent(int i) {
return (i - 1) / 2;
}
public static int leftChild(int i) {
return 2 * i + 1;
}
public static void main(String[] args) {
int[] array = {13,9,15,11,3,7,17,5,1};
System.out.println("初始状态：" + Arrays.toString(array));
// buildHeap(array);
buildHeap2(array);
System.out.println(Arrays.toString(array));//[17, 11, 15, 9, 3, 7, 13, 5, 1]
}
}
Result
初始状态 [13, 9, 15, 11, 3, 7, 17, 5, 1]
交换 [13, 9, 17, 11, 3, 7, 15, 5, 1]
交换 [13, 11, 17, 9, 3, 7, 15, 5, 1]
交换 [17, 11, 13, 9, 3, 7, 15, 5, 1]
交换 [17, 11, 15, 9, 3, 7, 13, 5, 1]
[17, 11, 15, 9, 3, 7, 13, 5, 1]
下沉排序
堆排序的主要工作还是在第二阶段完成的，下沉排序。这里我们将堆中最大的元素取出，和数组最后一个元素做交换，数组可操作的长度也相应的缩小一个位置。然后从堆顶开始进行下沉操作，无论循环多次都是从堆顶开始，直到数组可操作的长度最后为1。
动画
算法动画视频 地址 https://www.bilibili.com/video/av79323423/?p=3
[高清 720P] 堆排序_P3_堆有序 下沉排序 [最优化的质量和大小].flv
Code
package cn.study.sort;
import java.util.Arrays;
public class HeapSort1 {
public static void heapSort(int[] array) {
//堆有序
System.out.println("堆有序");
buildHeap2(array);
//下沉排序
System.out.println("下沉排序");
for (int i = 0; i < array.length - 1; i++) {
swap(array, 0, array.length - i - 1);
siftDown2(array, 0, array.length - i - 1);
}
}
//堆有序化：自底向上
public static void buildHeap(int[] array) {
//从数组第2个元素开始
for (int i = 1; i < array.length; i++) {
siftUp(array, i);
}
}
//堆有序化：自顶向下
public static void buildHeap2(int[] array) {
for(int i = parent(array.length - 1); i >= 0; i--){
siftDown(array, i);
}
}
//上浮：和添加元素的上浮不同，减少计算次数
public static void siftUp(int[] array, int i) {
int flag = i;
for(; i > 0 && array[i] > array[parent(i)]; i = parent(i)){
if(flag != i){break;}
flag = parent(i);
swap(array, i, parent(i));
System.out.println("交换：" + Arrays.toString(array));
}
}
//下沉
//i为当前节点，是它的左孩子和右孩子的父节点
//在左孩子和右孩子中找到元素值最大的一个，然后与父节点交换元素值。
public static void siftDown(int[] array, int i) {
while(leftChild(i) < array.length){
int l = leftChild(i);
if(l + 1 < array.length && array[l] < array[l + 1]){//如果有右孩子，并且右孩子元素的值比左孩子元素的值大
l++;//记录右孩子的索引值
}
if(array[l] < array[i]){//如果子节点的元素值比父节点小，就不用交换元素值
break;
}
swap(array, l, i);//将子节点的元素值与父节点的元素值交换
System.out.println("交换：" + Arrays.toString(array));
i = l;//记录被调整的子节点的索引
}//end of while
}
//下沉：考虑可操作的长度
//i为当前节点，是它的左孩子和右孩子的父节点
//在左孩子和右孩子中找到元素值最大的一个，然后与父节点交换元素值。
public static void siftDown2(int[] array, int i, int length) {
while(leftChild(i) < length){
int l = leftChild(i);//左孩子
if(l + 1 < length && array[l] < array[l + 1]){//如果有右孩子，并且右孩子元素的值比左孩子元素的值大
l++;//右孩子
}
if(array[l] < array[i]){//如果子节点的元素值比父节点小，就不用交换元素值
break;
}
swap(array, l, i);//将子节点的元素值与父节点的元素值交换
System.out.println("交换：" + Arrays.toString(array));
i = l;//记录被调整的子节点的索引
}//end of while
}
public static void swap(int[] array, int i, int j) {
if(i == j){return;}
//按位异或运算符"^"的运算规律是：两个操作数(二进制形式)的位中，相同则结果为0，不同则结果为1。
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
public static int parent(int i) {
return (i - 1) / 2;
}
public static int leftChild(int i) {
return 2 * i + 1;
}
public static void main(String[] args) {
int[] array = {13,9,15,11,3,7,17,5,1};
System.out.println("初始状态：" + Arrays.toString(array));
// buildHeap(array);//[17, 11, 15, 9, 3, 7, 13, 5, 1]
// buildHeap2(array);//[17, 11, 15, 9, 3, 7, 13, 5, 1]
heapSort(array);//[1, 3, 5, 7, 9, 11, 13, 15, 17]
System.out.println(Arrays.toString(array));//[17, 11, 15, 9, 3, 7, 13, 5, 1]
}
}
Result
初始状态 [13, 9, 15, 11, 3, 7, 17, 5, 1]
堆有序
交换 [13, 9, 17, 11, 3, 7, 15, 5, 1]
交换 [13, 11, 17, 9, 3, 7, 15, 5, 1]
交换 [17, 11, 13, 9, 3, 7, 15, 5, 1]
交换 [17, 11, 15, 9, 3, 7, 13, 5, 1]
排序
交换 [15, 11, 1, 9, 3, 7, 13, 5, 17]
交换 [15, 11, 13, 9, 3, 7, 1, 5, 17]
交换 [13, 11, 5, 9, 3, 7, 1, 15, 17]
交换 [13, 11, 7, 9, 3, 5, 1, 15, 17]
交换 [11, 1, 7, 9, 3, 5, 13, 15, 17]
交换 [11, 9, 7, 1, 3, 5, 13, 15, 17]
交换 [9, 5, 7, 1, 3, 11, 13, 15, 17]
交换 [7, 5, 3, 1, 9, 11, 13, 15, 17]
交换 [5, 1, 3, 7, 9, 11, 13, 15, 17]
[1, 3, 5, 7, 9, 11, 13, 15, 17]
喜欢本文的朋友，微信搜索「算法无遗策」公众号，收看更多精彩的算法动画文章