专栏首页yang0rangeJava常见排序算法详解——堆排序

Java常见排序算法详解——堆排序

转载请注明出处:https://www.jianshu.com/p/73ef54fb99f4

概念

二叉树

要了解堆首先得了解一下二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第 i 层至多有 2i - 1 个结点;深度为 k 的二叉树至多有 2k - 1 个结点;对任何一棵二叉树 T,如果其终端结点数为 n0,度为 2 的结点数为 n2,则n0 = n2 + 1。

树和二叉树的三个主要差别:

树的结点个数至少为 1,而二叉树的结点个数可以为 0 树中结点的最大度数没有限制,而二叉树结点的最大度数为 2 树的结点无左、右之分,而二叉树的结点有左、右之分 二叉树又分为完全二叉树(complete binary tree)和满二叉树(full binary tree) 如图:

满二叉树:一棵深度为 k,且有 2k - 1 个节点称之为满二叉树 完全二叉树:深度为 k,有 n 个节点的二叉树,当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至 n 的节点对应时,称之为完全二叉树

堆(二叉堆)可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示(普通的一般的二叉树通常用链表作为基本容器表示),每一个结点对应数组中的一个元素。

如下图,是一个堆和数组的相互关系

二叉堆一般分为两种:最大堆和最小堆。

最大堆:

最大堆中的最大元素值出现在根结点(堆顶) 堆中每个父节点的元素值都大于等于其孩子结点(如果存在)

最小堆:

最小堆中的最小元素值出现在根结点(堆顶) 堆中每个父节点的元素值都小于等于其孩子结点(如果存在)

原理

  1. 最大堆调整(Max_Heapify):从堆的倒数第一个非叶子节点作调整,使得子节点永远小于父节点。没有必要从叶子节点开始,叶子节点可以看作是已符合堆特点的节点。
  2. 创建最大堆(Build_Max_Heap):将堆所有数据重新排序
  3. 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整。 图解:列如我们有原始数字[2 10 9 5 6 1] 下面我们用堆排序排序 原始为:

第一次:

第二次

我们得到了

代码实现:

 /**
     * 堆排序的主要入口方法,共两步。
     */
    public void sort() {
        /*
         *  第一步:将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点,根节点就是它自己且自己以下值为最大。
         */
        int len = array.length - 1;
        int beginIndex = (len - 1) >> 1;
        for (int i = beginIndex; i >= 0; i--)
            maxHeapify(i, len);
        /*
         * 第二步:对堆化数据排序
         * 每次都是移出最顶层的根节点A[0],与最尾部节点位置调换,同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素,使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for (int i = len; i > 0; i--) {
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

    private void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 调整索引为 index 处的数据,使其符合堆的特性。
     *
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆(数组)的长度
     */
    private void maxHeapify(int index, int len) {
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引,默认左子节点。
        if (li > len) return;      // 左子节点索引超出计算范围,直接返回。
        if (ri <= len && array[ri] > array[li]) // 先判断左右子节点,哪个较大。
            cMax = ri;
        if (array[cMax] > array[index]) {  //若“<”这是从大到小
            swap(cMax, index);      // 如果父节点被子节点调换,
            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }

算法系列:

冒泡排序 选择排序 直接插入排序 二分插入排序 希尔排序 堆排序

完整代码:

Java和Kotlin代码我均放在了GitHub上,欢迎Star!

GitHub地址:https://github.com/yang0range/MyAlgorithm

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java常见排序算法详解—— 二分插入排序

    二分(折半)插入排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式,在速度上有一定提升。

    Demo_Yang
  • Java常见排序算法详解——直接插入排序

    将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录递增1的有序表。 插入排序是进行值移动,而是不值交换。所以在量较小的情况下插入排序性能要优于冒泡和...

    Demo_Yang
  • 谷歌官方组件Navigation你了解了吗?

    之前分别介绍了Android Studio3.3更新之后的Android Studio3.3的介绍 以及Android Studio3.3的使用 在更新之后...

    Demo_Yang
  • 数据结构之树

    树(Tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关...

    我是攻城师
  • 7-1 树结构 和 二叉树

    前面讲的都是 线性存储结构,而树是一种典型的非线性存储结构,一个元素可以有多个直接后继元素。

    TeeyoHuang
  • 拜托,别问我什么各种Tree了,干就完事!

    二叉排序树(Binary Sort Tree)又称二叉查找树、二叉搜索树。它或者是一棵空树;或者是具有下列性质的二叉树:

    我是程序员小贱
  • 云原生,企业云的未来

    引语:云原生是一个不断丰富的理念和技术体系,它在基础架构、应用程序和管理上都将深刻的影响和改变企业云的未来!

    SammyLiu
  • # 赫夫曼树

    * **最优二叉树:**树的带权路径长度为树中所有叶子结点的带权路径长度之和最小。

    用户1175783
  • 每天5分钟用C#学习数据结构(15)二叉树 Part 1

    如上图所示,A点称为根节点,它有两棵子树,分别以B、C为根,而以C为根的子树又可以分成两棵子树。

    Enjoy233
  • 6.3 遍历二叉树和线索二叉树

    1、在二叉树的一些应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理。

    闫小林

扫码关注云+社区

领取腾讯云代金券