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

算法渣-排序-堆排序

作者头像
码农戏码
发布2021-03-23 10:41:26
3580
发布2021-03-23 10:41:26
举报
文章被收录于专栏:DDD

没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法

定义

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆是一棵顺序存储的完全二叉树

其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆

其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆

举例来说,对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时,称之为堆:

(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)

(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整;

同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子

完全二叉树

完全二叉树的定义是建立在满二叉树定义的基础上的,而满二叉树又是建立在二叉树的基础上的。

二叉树

二叉树是树的特殊一种,具有如下特点:

  1. 每个结点最多有两颗子树,结点的度最大为2。
  2. 左子树和右子树是有顺序的,次序不能颠倒。
  3. 即使某结点只有一个子树,也要区分左右子树。
满二叉树

所有的分支结点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样就是满二叉树。就是完美圆满的意思,关键在于树的平衡

根据满二叉树的定义,得到其特点为:

  1. 叶子只能出现在最下一层。
  2. 非叶子结点度一定是2.
  3. 在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多。
完全二叉树

对于一个树高为h的二叉树,如果其第0层至第h-1层的节点都满。如果最下面一层节点不满,则所有的节点在左边的连续排列,空位都在右边。这样的二叉树就是一棵完全二叉树

在上图中,树1,按层次编号5结点没有左子树,有右子树,10结点缺失。树2由于3结点没有字数,是的6,7位置空挡了。树3中结点5没有子树。

上图就是一个完全二叉树

算法

利用堆顶记录的是最大(以大顶堆为例)关键字这一特性,每一轮取堆顶元素放入有序区,就类似选择排序每一轮选择一个最大值放入有序区,可以把堆排序看成是选择排序的改进。

  1. 将初始待排序关键字序列(R0,R1,R2....Rn)构建成大顶堆,此堆为初始的无序区;
  2. 将堆顶元素R[0]与最后一个元素R[n]交换,此时得到新的无序区(R0,R1,R2,......Rn-1)和新的有序区(Rn);
  3. 由于交换后新的堆顶R[0]可能违反堆的性质,因此需要对当前无序区(R0,R1,R2,......Rn-1)调整为新堆

不断重复此2、3步骤直到有序区的元素个数为n-1,则整个排序过程完成

演示

  1. 由一个无序序列建成一个堆
  2. 输出堆顶元素之后,调整剩余元素成为一个新的堆

1.构造堆

构造初始堆,将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)

数组是一个无序结构

因为(n/2-1)~0的节点才有子节点,n=5,(n/2-1) = 1 即1 0节点才有子节点

所以将1 0节点从下到上,从右到左的与它自己的子节点比较并调整最终形成大顶堆

1. 节点1和它的子节点3 4的元素进行比较,最大者作为父节点

2. 将节点0和它的子节点1 2的元素进行比较,最大者为父节点

3. 交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6

构造完成将一个无需序列构造成了一个大顶堆

2. 调整堆

将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

1. 将堆顶元素9和末尾元素4进行交换

2. 重新调整结构,使其继续满足堆定义

3. 再将堆顶元素8与末尾元素5进行交换,得到第二大元素8

4. 继续进行调整,交换,如此反复进行,最终使得整个序列有序

实现

代码语言:javascript
复制
/**
 *
 * a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

  b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

  c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

 * 整个排序过程,就是构造堆的过程
 *
 * 这儿写得利于理解一点,把最后一步改掉,循环从数组中把第一位取出来放到新数组,剩余的再去构造堆
 * @param array
 */
static void heapSort(int []array) {
    //原始数组
    int [] oriental = Arrays.copyOf(array,array.length);
    //最终排序好的数组
    int [] result = new int[array.length];

    int length = array.length;
    for ( int i = 0;i< length;i++) {
        //1.构造堆
        buildHeap(array);
        //构建完array[0]就是最大的元素,取出来放到排序好的数组
        result[i] = array[0];
        //[0]取走之后,一个新数组,再去构造堆
        array = Arrays.copyOfRange(array, 1,length-i);
    }
    System.out.println("finish:"+ Arrays.toString(result));
}

/**
 * 构造椎
 * @param array
 */
static void buildHeap(int []array) {
    //(n/2-1)~0的节点才有子节点
    for (int i= array.length/2 -1 ;i>=0;i--) {
//            System.out.println("i:"+i);
//            System.out.println("start:"+ Arrays.toString(array));
        int k = i;
        for (int left = k * 2 + 1; left < array.length; left = k * 2 + 1) {
           // System.out.println("build:"+ Arrays.toString(array));
            int max = left;
            int right = left + 1;
            //有右节点
            if (right < array.length) {
                if (array[right] > array[left]) {
                    max = right;
                }
            }
            //max是left子节点,那就交换左子节点与k
            if (array[max] > array[k]) {
                swap(array, max, k);
                // 下面就是非常关键的一步了
                // 如果子节点更换了,那么,以子节点为根的子树会不会受到影响呢?
                // 所以,循环对子节点所在的树继续进行判断
                k = left;
            } else {
                break;
            }
        }
    }
    //System.out.println("  end:"+ Arrays.toString(array));
}

详细代码:https://github.com/zhuxingsheng/javastudy/tree/master/src/main/java/com/jack/algorithms/sort

复杂度

Best

Average

Worst

Memory

Stable

n log(n)

n log(n)

n log(n)

1

No

参考资料

图解排序算法(三)之堆排序

图解堆排序

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-12-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 码农戏码 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 定义
      • 完全二叉树
    • 算法
      • 演示
        • 1.构造堆
        • 2. 调整堆
    • 实现
    • 复杂度
    • 参考资料
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档