前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >堆排序算法原理

堆排序算法原理

作者头像
Java架构师必看
发布2021-04-30 15:48:34
4080
发布2021-04-30 15:48:34
举报
文章被收录于专栏:Java架构师必看

堆排序算法原理

强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。 

一、什么是堆


【1】堆是一个完全二叉树,特点是从上往下,从左往右以次排列的; 【2】在堆的数据结构中,堆中的最大值总是位于根节点,所有父节点都满足大于等于其子节点;

二、创建堆


需求将下面的二叉树,变成一个平衡二叉树。

【思路】:【1】先创建一个 heapfiy() 方法,从4号节点开始判断是否大于其孩子节点,如果否,则进行交换,并递归对4号节点进行 heapfiy() 操作。具体看代码操作; 【2】创建推是需要从h(树的高度)-1 层最后一个节点(3号)向上调用 heapfiy() 方法。最终就会得到堆。 【3】将上面的树转为一维数组[4,9,3,5,1,8]; 【4】父节点计算公式:parent = (i - 1) / 2; 【5】左子节点计算公式:c1 = 2i + 1; 【6】右子节点计算公式:c2 = 2i + 2;

代码语言:javascript
复制
/**
 * Created by Administrator on 2020/3/21 0021. 创建堆
 */
public class HeapSortDemo {
    /**@desc 说明1 heapfy 方法
     * @param i : 表示对那个节点进行堆的heapify
     * @param h : 表示堆的节点个数
     */
    public void heapfiy(Integer[] arr, int i, int h){
        //1、计算树的节点个数,减1代表下标
        int n = h;

        //递归需要定义一个出口
        if(i >= (n-2)/2){
            return;
        }
        //计算 i 的左子树和右子树
        int c1 = i * 2 + 1;
        int c2 = i * 2 + 2;
        int max = i;
        //判断左子树是否大于 max 下标的值
        if(c1 < n && arr[c1] > arr[max] ){
            max = c1;
        }

        //判断右子树是否大于 max 下标的值
        if(c2 < n && arr[c2] > arr[max] ){
            max = c2;
        }

        //如果 i == max 说明就是堆,否则就递归 heapfiy 调用
        if(max != i){
            swap(arr,max,i);
            heapfiy(arr,max,h);
        }
    }

    //说明2: 数组到序递归 heapify,从最后一个节点的parent;
    public void build_heap(Integer arr[],int n){
        //确定最后一个节点的父节点
        int parent = (n - 2) / 2;
        //由下向上堆排序
        for(int i = parent; i >= 0; i--){
            heapfiy(arr,i,n);
        }
    }

    //数据交换
    public void swap(Integer[] arr,int i,int n){
        int temp ;
        temp = arr[i];
        arr[i] = arr[n];
        arr[n] = temp;
    }
}

三、堆排序


将堆的根结点与最后一位进行交换,然后将最后一位砍断,对剩余的数组进行递归构建堆并进行首尾交换截取即可。

代码语言:javascript
复制
//堆排序
public void heapSort(Integer[] arr){
    //节点的个数
    //循环构建堆对象,i表示数组参与堆的个数
    for(int i = arr.length; i > 0; i--){
        build_heap(arr,i);
        //对第一个节点和最后一个进行交换
        swap(arr,0,i-1);
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、什么是堆
    • 二、创建堆
    • 三、堆排序
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档