ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式

admin 2个月前 (06-17) 科技 17 1

是否记得我们在之前的学习中有学习到二叉树 遗忘的小伙伴们请查看:完全二叉树的界说。

https://blogs.chaobei.xyz/archives/shuju2

二叉堆

二叉堆实在就是一个完全二叉树 一起温习一下吧:关于二叉树和满二叉树以及完全二叉树的基本观点。

二叉树

  • 每个节点下挂元素不跨越2
  • 而且元素都是根据一定纪律排列的

二叉树纪律

根据前人的总结,我们可以得出以下结论。

  • 一个深度为K 的二叉树,最多包罗节点数 2的k次方-1
  • 二叉树指定n 层级所包罗的节点数为 2的n-1次方

满二叉树

从字面意思我们可以明白到:这个二叉树它是一种饱和的状态,顾名思义称作是满二叉树。

完全二叉树

除去二叉树的叶子节点,所有节点都包罗有两个节点,而且节点都是根据一定顺序排列的,这样的二叉树被称作是完全二叉树

二叉堆类型

在上面我们已经提到过。二叉堆就是一种完全二叉树、二叉树的观点也已经领会到了。固然,现在应该剖析二叉堆有有哪些性子

  • 最大堆
  • 最小堆

最大堆

最大堆的父节点元素的值都大于即是其两个子元素的值

ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第1张

最小堆

反之,最小堆父节点元素的值,都小于即是其两个子元素的值
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第2张

二叉堆的堆顶部 则是这个堆序列最大或者最小的元素。

二叉堆的自我调整

二叉堆的自我调整,有以下几种情形:

  • 新元素的插入
  • 元素的删除
  • 构建二叉堆

我们以最上面的最小堆为例,讲述若何将一个元素插入二叉堆、若何删除一个元素、若何来构建一个二叉堆。

插入一个节点

根据上面最小堆的顺序,我这里再插入几个其他元素利便考察。假设这里我插入一个元素1
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第3张

元素1<元素6 举行上浮。子节点与父节点举行换取位置
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第4张

元素1<元素3 举行上浮。子节点与父节点举行换取位置
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第5张

元素1<元素2 举行上浮。到达堆顶部。
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第6张

删除一个元素

当前元素与子节点中最小元素举行对照、大于则交流位置下沉

假设我们删除最顶层的元素1
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第7张

二叉堆为了保证树的结构、将二叉堆内里尾部元素6填充到被删除的位置。
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第8张

当前元素6 与两个子元素内里最小元素 举行对照。大于则下沉
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第9张

当前元素6 > 3 举行换取位置。元素6到达尾部。
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第10张

纪律:二叉堆的删除元素和新增元素刚好是相反的

构建一个二叉堆

构建二叉堆、实在就是将一个原有的、无序的、完全二叉树给他构建成有序的二叉堆。

假设我们来构建一个最小堆 我们这里拿到一个无序的完全二叉树如图:
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第11张

划重点:构建最小堆就是将非叶子节点举行下沉

1、操作元素5 元素5小于元素8 不举行移动
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第12张

2、操作元素1 元素1小于元素5 不举行移动
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第13张

3、操作元素7 省略步骤。最终效果如下:
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第14张

4、操作元素3 省略步骤。最终效果如下:
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第15张

至此,我们的无序完全二叉树已经变成了一个有序的二叉最小堆

代码实现

二叉堆虽然是一颗完全二叉树,然则其存储方式是顺序存储,使用的是数组、而不是链式指针。
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第16张
ug环球app下载:数据结构 9 基础数据结构 二叉堆 领会二叉堆的元素插入、删除、构建二叉堆的代码方式 第17张

我们可以发现如下纪律:

  • 父元素左边子元素位置 = 2*父元素下标 + 1
  • 父元素右边子元素位置 = 2*父元素下标 + 2
public static void main(String[] args) {
        int[] array = {7, 1, 3, 5, 6, 4, 2, 8, 9};
        buildBinaryHeap(array);
        System.out.println(Arrays.toString(array));
    }

    public static void buildBinaryHeap(int[] array) {
        //除去叶子节点、将每个节点举行下沉操作
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            sinking(array, i);
        }
    }

    /**
     * 构建二叉堆、让当前元素下沉
     *
     * @param array     被操作的数组
     * @param itemIndex 当前元素下标
     */
    public static void sinking(int[] array, int itemIndex) {
        //数组长度
        int length = array.length - 1;
        //父节点值
        int parent = array[itemIndex];

        //默认操作的是左孩子
        int childIndex = 2 * itemIndex + 1;

        while (childIndex < length) {

            //存在右边子元素、而且右边子元素值小于左边
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                //切换到右边元素
                childIndex++;
            }

            //小于即是则无需交流
            if (parent <= array[childIndex]) break;

            //无需交流、只需要将子元素移动到父元素位置即可
            array[itemIndex] = array[childIndex];
            itemIndex = childIndex;

            //改变左右子元素的下标
            childIndex = 2 * itemIndex + 1;
        }
        //最终将父元素移动到指定位置即可。
        array[itemIndex] = parent;
    }

代码示例

https://gitee.com/mrc1999/Data-structure

小结

通过本节的学习,应该需要掌握二叉堆这个主要的数据结构、若何将一个完全二叉树构建成一个二叉堆、而且二叉堆在插入元素、和删除元素时刻若何将原来的结构保持稳定的。这该是我们学习的。
下一节将继续学习二叉堆的堆排序、我们一起加油!

参考

https://mp.weixin.qq.com/s/cq2EhVtOTzTVpNpLDXfeJg

,

欧博注册网址

www.cx11yl.cn欢迎进入欧博网址(Allbet Gaming),欧博网址开放会员注册、代理开户、电脑客户端下载、苹果安卓下载等业务。

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:661
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1035
  • 评论总数:279
  • 浏览总数:8813