十大经典排序算法之堆排序（Java语言）
十大经典排序算法之堆排序（Java语言）
文章目录
什么是堆
如何进行堆排序呢
用数组构建一个堆
上代码
什么是堆
在了解什么是堆之前一定要先了解什么是完全二叉树
看一下百度百科的介绍
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
百度百科拗口版性质介绍，能看懂上面的就行，下面的大概看下
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）
(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。
那么在了解到什么是完全二叉树之后，我们再来看什么是堆
堆有以下两个性质
1 堆中某个节点的值总是不大于或不小于其父节点的值；
2 堆总是一棵完全二叉树。
其中堆顶就对应二叉树的根
堆又分为大顶堆和小顶堆，根据堆的第一个性质来进行区分
当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆，反之为小顶堆
如何进行堆排序呢
堆排序，其实就是每次构造出一个大顶堆或者小顶堆，然后取出堆顶的值，再将剩下的值重新构造成大顶堆或者小顶堆，最终到堆里的值全部取出来，取出来的数就是排好序的
用数组构建一个堆
因为堆是一颗完全二叉树，所以我们可以用数组来对其进行存储
对于用数组存储的二叉树，我们可以用如下方法来定义：
假设当前节点的下标为 n
1、那么他的左子节点的下标 2*n + 1
2、那么他的右子节点的下标 2*n + 2
3、他左边的节点是 n-1，如果当前节点是第 h 层的最左节点，那么第h-1层的最右节点的下标就是 n-1
4、根据1、2可以推出来n节点的父节点是 (n-1)/2，不管当前节点是父节点的左子节点还是右子节点，都用 (n-1)/2就行了，因为整型数字相除小数点后面的会被截断
那么有了上面四条性质，我们就可以开始动手了
1、假设我们要构建的堆是大顶堆，那么根据大顶堆的性质，任意节点都比它的左右子节点要大，所以我们肯定有个heapify方法，该方法调整指定节点和其子节点的位置，并且继续调整被调整的子节点和孙子节点的关系，直到没有调整或者到数的最底层
2、然后我们要有构造大顶堆的方法，构造大顶堆就是从最后一个节点的父节点开始调整，接设最后一个节点的父节点是n，那么我们就将n，n-1，n-2 ··· ··· 0，这些节点逐次，从大到小调用heapify方法，这些节点都调整完成后，大顶堆就构造完成了
3、接下来就开始将堆顶和堆尾互换，并砍断堆尾的操作了，由于互换之前，这是一个符合条件的大顶堆，但是换完只有只有一个堆顶这里不满足了，那么我们重新调整一下堆顶的三个元素就可以，还是调用heapify方法，这个方法会自上而下的重新调整堆，使其成为一个大顶堆
堆排序的性质
中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
堆排序 Heap n*logn n*logn n*logn 1 不稳定
上代码
/**
* 交换第n和m个元素
*/
private static void swap(int arr[], int n, int m){
int temp = arr;
arr = arr;
arr = temp;
}
/**
* 调整指定节点和其子节点
* @param tree 整棵树
* @param n 数组长度，树的元素个数
* @param i 要调整的节点的下标
*/
private static void heapIfy(int tree[], int n, int i){
if(i >= n){
return;
}
int c1 = 2 * i + 1;//左子节点的下标
int c2 = 2 * i + 2;//右子节点的下标
int max = i;//假设父节点是最大的
//找出最大值的下下标
if(c1 < n && tree > tree){
max = c1;
}
if(c2 < n && tree > tree){
max = c2;
}
if(max != i){//如果最大值不是父节点，需要做换位置操作
swap(tree, max, i);
//此时，i节点被换成最大值了，符合大顶堆的性质
//但是换到下面的节点不能保证比他的两个子节点都要大
//所以被换位置的节点继续调整
heapIfy(tree, n, max);
}
}
/**
* 完整构建大顶堆
* @param arr 用于构建堆的数组
* @param n 堆的最后一个节点的下标
*/
private static void buildHeap(int arr[],int n){
int lastNode = n - 1;
int parent = (lastNode - 1) / 2;
for (int i = parent; i >= 0; i--){
heapIfy(arr, n, i);
}
}
/**
* 堆排序
* @param arr 待排数组
*/
public static void sort(int arr[]){
buildHeap(arr, arr.length);//先构造大顶堆
//每次构建堆后将根节点和最后一个节点进行交换
//然后砍断最后一个节点
//所以从最后一个节点向前循环
for (int i = arr.length - 1; i > 0; i--){
swap(arr, 0, i);
heapIfy(arr, i, 0);
}
}
————————————————
版权声明：本文为CSDN博主「qq_34912889」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_34912889/article/details/105690644
页:
[1]