详解堆排序

2020年5月19日15:22:43算法评论50阅读模式

什么是堆

首先是一个完全二叉树,分为大顶堆小顶堆
大顶堆 :
每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。
小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。
注意:
每个节点的左右孩子节点的大小关系并没有限定。文章源自随机的未知-https://sjdwz.com/11143.html

大顶堆举例

如图:文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
大顶堆举例

首先其为一个完全二叉树,且其每个节点的值都大于或者等于其左右孩子节点的值。
完全二叉树从上到下,从左到右依次编号,就可以将其进行顺序存储,我们从根节点开始,从0开始编号,存入数组如下:文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
举例大顶堆存入数组

堆特点

由大顶堆定义知道,如果我们从上到下,从左到右,根节点开始从0编号进行顺序存储的话,并将数组记为arr;
我们可以得到如下式子:
arr[i] >= arr[ 2i + 1] && arr[ i ] >= arr[ 2i + 2];
其中 2i + 1为第 i 个节点的左孩子节点的编号。2i + 2为第 i 个节点的右孩子节点的编号;
同理得小顶堆的特点:
arr[i] <= arr[ 2i + 1] && arr[ i ] <= arr[ 2i + 2];文章源自随机的未知-https://sjdwz.com/11143.html

堆排序基本思想

本文以大顶堆为例,进行讲解。
算法步骤如下:
1、首先将待排序序列构建成一个大顶堆(存入数组中),那么这时,整个序列的最大值就是堆顶的根节点;
2、将堆顶元素与最后一个元素交换,那么末尾元素就存入了最大值;
3、将剩余的 n - 1个元素重新构建成一个大顶堆,重复上面的操作;
反复执行,就能得到一个有序序列了。文章源自随机的未知-https://sjdwz.com/11143.html

举例

给定一个待排序序列数组 arr = [ 0 , 2, 4, 1 , 5 ];
先构建成一个完全二叉树如下;文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
初始状态

构建堆

我们从最后一个非叶子节点开始,从左至右,从下到上,开始调整
最后一个非叶子节点的索引即 arr.length / 2向下取整 - 1 ,对于此例就是 5 / 2向下取整 - 1 = 2 - 1 = 1;
即值为2的节点;
详解堆排序文章源自随机的未知-https://sjdwz.com/11143.html

我们用左右孩子节点的最大值与该节点进行比较;
此时我们发现它的左右孩子节点的最大值为5,大于2,进行交换;文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
构建堆2

然后处理下一个非叶子节点,即刚才的索引减去1; 1 - 1 = 0;
即:文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
左右孩子节点为5和4,5最大,且大于该节点的值,发生交换;文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
这时我们发现了一个问题:
值为0的节点的左右节点又比该节点大了,又不满足大顶堆的定义了文章源自随机的未知-https://sjdwz.com/11143.html

继续进行调整:文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
构建堆5

对非叶子节点调整完毕,构建大顶堆完成。文章源自随机的未知-https://sjdwz.com/11143.html

交换

将堆顶元素与末尾元素进行交换,使得末尾元素最大。文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
堆顶元素与末尾元素交换

当交换完毕后最大的元素已经到达数组末尾;文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
第一次交换后

对数组中其他元素进行排序即可。文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
剩下的四个元素进行调整

进行交换:文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
第二大元素归位

剩下的元素调整并交换后:文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
第三大元素归位

剩下的元素调整并交换后:文章源自随机的未知-https://sjdwz.com/11143.html

详解堆排序
第三大元素归位
详解堆排序
第四大元素归为

此时也意味着排序完成了。文章源自随机的未知-https://sjdwz.com/11143.html

代码

先说下调整的代码;
我们需要三个参数,待排序的数组,数组的长度,还有一个就是调整的哪一个非叶子节点;文章源自随机的未知-https://sjdwz.com/11143.html

 /**
     * author:微信公众号:code随笔
     * @param arr 待排序的数组
     * @param i   表示等待调整的哪个非叶子节点的索引
     * @param length 待调整长度
     */
    public static void adjustHeap(int arr[],int i,int length){
        //非叶子节点的值
        int notLeafNodeVal = arr[i];
        //k的初始值为当前非叶子节点的左孩子节点的索引
        //k = 2 * k + 1表示再往左子节点找
        for(int k = i * 2 + 1;k<length;k=2 *k + 1){
            //如果k + 1还在待调整的长度内,且右子树的值大于等于左子树的值
            //将k++,此时为当前节点的右孩子节点的索引
            if(k+1<length && arr[k] < arr[k+1]){
                k++;
            }
            //如果孩子节点大于当前非叶子节点
            if(arr[k] > notLeafNodeVal){
                arr[i] = arr[k];//将当前节点赋值为孩子节点的值
                i = k;//将i赋值为孩子节点的值,再看其孩子节点是否有比它大的
            }else{
                break;//能够break的保证是,我们是从左至右,从下到上进行调整的
                //只要上面的不大于,下面的必不大于
            }
        }
        //循环结束后,将i索引处的节点赋值为之前存的那个非叶子节点的值
        arr[i] = notLeafNodeVal;
    }

再说下堆排序代码,看好注释;文章源自随机的未知-https://sjdwz.com/11143.html

//堆排序方法
    public static void heapSort(int arr[]){
        //进行第一次调整
        for(int i=arr.length/2 - 1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }

        for(int j=arr.length - 1;j>0;j--){
            //进行交换
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            //调整长度为j的那些
            //这里为什么填0呢
            //因为我们第一次调整的时候从左到右,从下到上调整的;
            //交换时只是变动了堆顶元素和末尾元素
            //末尾元素我们不用去管,因为已经是之前长度最大的了
            //只需要把当前堆顶元素找到合适的位置即可
            adjustHeap(arr,0,j);
        }
    }

完整代码文章源自随机的未知-https://sjdwz.com/11143.html

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {

        int [] arr = new int[]{0 , 2,  4,  1 , 5};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));

    }
    //堆排序方法
    public static void heapSort(int arr[]){
        //进行第一次调整
        for(int i=arr.length/2 - 1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }

        for(int j=arr.length - 1;j>0;j--){
            //进行交换
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            //调整长度为j的那些
            //这里为什么填0呢
            //因为我们第一次调整的时候从左到右,从下到上调整的;
            //交换时只是变动了堆顶元素和末尾元素
            //末尾元素我们不用去管,因为已经是之前长度最大的了
            //只需要把当前堆顶元素找到合适的位置即可
            adjustHeap(arr,0,j);
        }
    }
    /**
     * author:微信公众号:code随笔
     * @param arr 待排序的数组
     * @param i   表示等待调整的哪个非叶子节点的索引
     * @param length 待调整长度
     */
    public static void adjustHeap(int arr[],int i,int length){
        //非叶子节点的值
        int notLeafNodeVal = arr[i];
        //k的初始值为当前非叶子节点的左孩子节点的索引
        //k = 2 * k + 1表示再往左子节点找
        for(int k = i * 2 + 1;k<length;k=2 *k + 1){
            //如果k + 1还在待调整的长度内,且右子树的值大于等于左子树的值
            //将k++,此时为当前节点的右孩子节点的索引
            if(k+1<length && arr[k] < arr[k+1]){
                k++;
            }
            //如果孩子节点大于当前非叶子节点
            if(arr[k] > notLeafNodeVal){
                arr[i] = arr[k];//将当前节点赋值为孩子节点的值
                i = k;//将i赋值为孩子节点的值,再看其孩子节点是否有比它大的
            }else{
                break;//能够break的保证是,我们是从左至右,从下到上进行调整的
                //只要上面的不大于,下面的必不大于
            }
        }
        //循环结束后,将i索引处的节点赋值为之前存的那个非叶子节点的值
        arr[i] = notLeafNodeVal;
    }
}

时间复杂度

在建初始堆时,其复杂度为;
交换操作需 n-1 次;
重建堆的过程中近似为;
堆排序时间复杂度为。文章源自随机的未知-https://sjdwz.com/11143.html

稳定性

堆排序是不稳定的:
比如:10,9,6,9;
如图:
详解堆排序
当堆顶元素10和末尾元素交换后,两个9的相对位置发生改变。文章源自随机的未知-https://sjdwz.com/11143.html

欢迎关注

欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11143.html

扫描下方的二维码或者微信搜一搜即可关注我的微信公众号:随机的未知
详解堆排序文章源自随机的未知-https://sjdwz.com/11143.html

文章源自随机的未知-https://sjdwz.com/11143.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
算法最后更新:2022-2-24
  • 本文由 发表于 2020年5月19日15:22:43
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11143.html
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
算法

详解归并排序

基本思想 归并排序的基本思想是: 先将序列一次次分成子序列,直到子序列长度为1; 再将已有序的子序列合并,得到完全有序的序列。 可以看出归并排序运用了 分而治之的思想 。 例子 输入数组 < 2, 5...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定