堆的插入与删除维护大根堆,为什么需要俩个不同的方法(java)

   public void offer(int val) {//插入操作
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;//11
        siftUp(usedSize-1);
    }
   public void siftUp(int child) {
        int parent = (child-1)/2;
        while (parent >= 0) {
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }


    public int poll() {//删除操作,将首元素和尾元素互换后维修大根堆
        if(isEmpty()) {
            return -1;
        }
        int old = elem[0];
        swap(0,usedSize-1);
        usedSize--;
        siftDown(0,usedSize);
        return old;
    }
    public void siftDown(int parent,int end) {
        int child = 2*parent+1;
        while (child < end) {
            if(child+1 < end && elem[child] < elem[child+1]) {
                child++;
            }
            //child下标 就是 左右孩子的最大值
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

在堆(无论是大根堆还是小根堆)的插入和删除操作中,需要两个不同的方法来维护堆的性质。这是因为插入和删除操作对堆的影响不同,因此维护堆性质的方式也不同。

  1. 插入操作(siftUp):

    • 当新的元素被添加到堆的末尾时,它可能破坏堆的性质。因为新元素是最后被添加的,它总是处于叶子节点的位置。
    • 要修复这个问题,我们需要将新元素与其父节点进行比较,并根据需要交换它们的位置。这个过程会一直向上进行,直到新元素到达正确的位置,或者它不再比其父节点大(对于大根堆)。
    • 因此,siftUp 方法是从下往上调整堆的,它确保新插入的元素在堆中正确地“上浮”到合适的位置。
  2. 删除操作(通常是删除堆顶元素,然后siftDown):

    • 当堆顶元素(对于大根堆来说,是最大值)被删除时,我们需要用堆的最后一个元素来替换堆顶的位置,并重新调整堆以保持其性质。
    • 由于新放在堆顶的元素可能小于其子节点,我们需要将它“下沉”到正确的位置。这通常是通过与较大的子节点进行比较和交换来实现的。
    • siftDown 方法是从上往下调整堆的,它确保新放在堆顶的元素在堆中正确地“下沉”到合适的位置。

简而言之,siftUp 和 siftDown 方法的目的是在插入和删除操作后重新调整堆,以确保它仍然满足堆的性质(即父节点的值总是大于或等于其子节点的值,对于大根堆来说)。这两个方法分别处理从底部添加新元素和从顶部删除元素的情况,因此它们的实现方式有所不同。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/611276.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python学习笔记------json

json简介 JSON是一种轻量级的数据交互格式。可以按照JSON指定的格式去组织和封装数据 JSON本质上是一个带有特定格式的字符串 主要功能&#xff1a;json就是一种在各个编程语言中流通的数据格式&#xff0c;负责不同编程语言中的数据传递和交互 为了让不同的语言能够相互通…

luceda ipkiss教程 69:导出器件或者线路的三维模型

ipkiss 3.12版加入write_obj函数&#xff0c;可以直接输出器件的三维模型。 如&#xff0c;输出自定义的mmi的三维模型&#xff1a; 代码如下&#xff1a; from si_fab import all as pdk from ipkiss3 import all as i3class MMI1x2(i3.PCell):"""MMI with …

【C++】学习笔记——优先级队列

文章目录 十、优先级队列1. priority_queue的介绍2. 优先级队列如何使小的数据优先级高3. 仿函数介绍4. priority_queue的模拟实现 补&#xff1a; 反向迭代器未完待续 十、优先级队列 1. priority_queue的介绍 优先级队列 其实也不属于队列&#xff0c;它跟 stack 和 queue …

【MQTT】mosquitto 的 “下载、交叉编译、使用” 详细教程,手把手搭建一个MQTT Broker

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

ARIMA模型在河流水质预测中的应用_含代码

#水质模型 #时间序列 #python应用 ARIMA 时间序列模型简介 时间序列是研究数据随时间变化而变化的一种算法&#xff0c;是一种预测性分析算法。它的基本出发点就是事物发展都有连续性&#xff0c;按照它本身固有的规律进行。ARIMA(p,d,q)模型全称为差分自回归移动平均模型 (A…

单链表经典oj题(2)

前言 这次将要把剩下的oj题将以图解和自己的理解把它讲解完&#xff0c;希望对大家有所帮助&#xff0c;这次的讲解也是干货 第一题 21. 合并两个有序链表 - 力扣&#xff08;LeetCode&#xff09; ok这次就简单点&#xff0c;大家自己去看题目了 将两个升序链表合并为一个…

【Linux】进程的七大状态详解!

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …

如何查看centos7中Java在哪些路径下

在 CentOS 7 上&#xff0c;你可以通过几种方式查找安装的 Java 版本及其路径。以下是一些常用的方法&#xff1a; 1. 使用 alternatives 命令 CentOS 使用 alternatives 系统来管理同一命令的多个版本。你可以使用以下命令来查看系统上所有 Java 安装的配置&#xff1a; su…

C++动态内存管理:与C语言动态内存管理的差异之争

当你改错一行代码的时候&#xff1a; 当你想要重构别人的代码时&#xff1a; 目录 前言 一、C/C的内存分布 二、C/C语言中的动态内存管理 三、new与delete的实现原理 总结&#xff1a; 前言 在C中&#xff0c;内存管理是一个至关重要的主题。正确地管理内存可以避免内存泄…

上海AI Lab开源首个可替代GPT-4V的多模态大模型

与开源和闭源模型相比&#xff0c;InternVL 1.5 在 OCR、多模态、数学和多轮对话等 18 个基准测试中的 8 个中取得了最先进的结果。 上海AI Lab 推出的 InternVL 1.5 是一款开源的多模态大语言模型 (MLLM)&#xff0c;旨在弥合开源模型和专有商业模型在多模态理解方面的能力差距…

二、SPI协议

文章目录 总述1.SPI接口2. SPI工作模式3. SPI通信时序4. SPI协议 对比 UART协议&#xff08;上一篇文章刚介绍过uart协议&#xff0c;这里来对比一下&#xff09; 总述 SPI&#xff08;Serial Peripheral Interface&#xff09;是一种高速的、全双工、同步的串行通信总线&…

【影片欣赏】【指环王】【魔戒:国王归来 The Lord of the Rings: The Return of the King】

往期魔戒博客见&#xff1a; 【影片欣赏】【指环王】【魔戒&#xff1a;护戒使者 The Lord of the Rings: The Fellowship of the Ring】 【影片欣赏】【指环王】【魔戒&#xff1a;双塔奇谋 The Lord of the Rings: The Two Towers】 2004年发行&#xff0c;Special Extend…

副业兼职没那么难,视频号带货,1天稳定500,适合新手操作

向大家推荐一个项目&#xff1a;视频号书单号带货玩法。我已经实践了一段时间&#xff0c;并成功售出了1200多单&#xff0c;赚取了2万多元。这个项目表现相当出色&#xff0c;强烈推荐给大家&#xff01; 周周近财&#xff1a;让网络小白少花冤枉钱&#xff0c;赚取第一桶金 …

Linux vscode push报错fatal: Authentication failed

注意啊&#xff0c;Git基于密码的身份验证已经被删除了&#xff0c;所以这个报错发生时无论密码正确与否&#xff0c;以及参考比较旧的改bug教程&#xff0c;都没法提交。进入提示的网址&#xff0c;生成个人访问令牌就好了

200-500人规模工厂网络方案(中小企业网络)

一、方案概述 工厂一般有单独的弱电房&#xff0c;类似这种 里面采用的方案如下&#xff1a; 主要考虑有线、无线、财务、办公、访客等业务&#xff0c;便于维护管理和后续扩容 还需要 Wi-Fi覆盖零死角高速率&#xff0c;工作不卡顿 同时考虑AV反病毒、IPS入侵防御、用户准…

【MySQL数据库开发设计规范】之命名规范

欢迎点开这篇文章&#xff0c;自我介绍一下哈&#xff0c;本人姑苏老陈 &#xff0c;是一名JAVA开发老兵。 本文收录于 《MySQL数据库开发设计规范》专栏中&#xff0c;该专栏主要分享一些关于MySQL数据库开发设计相关的技术规范文章&#xff0c;定期更新&#xff0c;欢迎关注&…

python自动化生成ppt

使用Python和python-pptx创建PPT 在这篇博客中&#xff0c;我们将探讨如何使用Python库python-pptx来创建一个简单的PowerPoint演示文稿&#xff08;PPT&#xff09;。这个库允许我们以编程方式创建幻灯片、添加文本、图片、表格和自定义形状。 安装python-pptx 首先&#x…

智能助手上线,大模型提供云服务专属顾问

业务背景 在使用云服务的时候&#xff0c;当您遇到复杂问题&#xff0c;如配置、关联或计费方式不明确时&#xff0c;可能需要向客服提交工单进行技术沟通。在漫长的工作过程中&#xff0c;耗费了宝贵的时间和精力。 2024 年 4 月&#xff0c;百度智能云正式推出了融合文心大…

单调栈:(C++)

在题目的要求中&#xff0c;存在先进后出&#xff08;即在前面的数据需要遍历到后面的某一数据时才能确定计算值&#xff09;单调栈在一部分解题场景中避免了暴力解法的高时间复杂度问题&#xff0c;但是在做题过程中视情况而定&#xff0c;有些题目的最优解不一定使用单调栈&a…
最新文章