【数据结构】堆排序原理及实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【数据结构】堆排序原理及实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1924字，纯文字阅读大概需要3分钟。

内容图文

1.堆是一颗完全二叉树。

2.建立大根堆进行排序步骤

 

 

 

 

1）从第一个非叶子点开始堆化，一直到根节点

2）每次将根节点（最大值）放到最后面 重新堆化

/**
 * @Description:堆排
 * @Author: cckong
 * @Date:
 */
public class heapsort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 2, 6, 7, 8, 9, 10, 1, 12, 4, 21};
        int len=arr.length;
        //从第一个非叶子节点开始堆化 一直到根节点
        for(int i=len/2-1;i>=0;i--){
            heapify(arr,i,len);
        }
        for(int tmp:arr) System.out.print(tmp+" ");
        //开始排序
        for(int i=len-1;i>0;i--){
            swap(arr,0,i);//将大根堆的根节点（目前的最大值） 放到当前最后一位
            heapify(arr,0,i);//将剩余的结点重新堆化 长度减少1位
        }
        System.out.println();
        for(int tmp:arr) System.out.print(tmp+" ");
    }
    /**
    * @Description: 堆化操作
    * @Param:  建堆数组arr 开始堆化的位置i    最大长度len
    * @return:  null
    * @Author: cckong
    * @Date: 2021/4/12
    */
    public static void heapify(int[] arr,int i,int len){
        int tmp=arr[i];
        //注意for循环条件 从根的左子开始 每次都要去子的子结点（孙子结点）所以是k=2k+1
        for(int k=2*i+1;k<len;k=2*k+1){
            if(k+1<len&&arr[k+1]>arr[k]) k++;//父 左子 右子 在左右子选出最大的那个变为新父节点
            if(arr[k]>arr[i]){
                arr[i]=arr[k];//将当前i值替换成k值
                i=k;//i变k继续向下堆化
            }else {break;}
        }
        arr[i]=tmp;//最后一步进行赋值
    }
    /**
    * @Description: 交换函数
    * @Param:  需要排序的数组arr   交换的位置 i j
    * @return:  null
    * @Author: cckong
    * @Date: 2021/4/12
    */
    public static void swap(int[] arr,int i,int j){
        int tmp=arr[i];arr[i]=arr[j];arr[j]=tmp;
    }
}

 

 

3.小根堆只要改上面堆化的大于号改为小于号

/**
     * @Description: 堆化操作
     * @Param:  建堆数组arr 开始堆化的位置i    最大长度len
     * @return:  null
     * @Author: cckong
     * @Date: 2021/4/12
     */
    public static void heapify(int[] arr,int i,int len){
        int tmp=arr[i];
        //注意for循环条件 从根的左子开始 每次都要去子的子结点（孙子结点）所以是k=2k+1
        for(int k=2*i+1;k<len;k=2*k+1){
            if(k+1<len&&arr[k+1]<arr[k]) k++;//父 左子 右子 在左右子选出最大的那个变为新父节点
            if(arr[k]<arr[i]){
                arr[i]=arr[k];//将当前i值替换成k值
                i=k;//i变k继续向下堆化
            }else {break;}
        }

 

内容总结

以上是互联网集市为您收集整理的【数据结构】堆排序原理及实现全部内容，希望文章能够帮你解决【数据结构】堆排序原理及实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---