数学建模社区-数学中国

标题: 十大经典排序算法之堆排序（Java语言） [打印本页]

作者: 杨利霞 时间: 2020-4-23 15:00
标题: 十大经典排序算法之堆排序（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[n];
arr[n] = arr[m];
arr[m] = 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[c1] > tree[max]){
      max = c1;
}
if(c2 < n && tree[c2] > tree[max]){
      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

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)