【数据结构】堆

文章目录

  • 优先级队列
    • 几点说明
    • 小根堆
    • 大根堆
  • 建堆算法
    • 向下调整算法 & 初始化堆
    • 代码:
    • 向上调整算法 & 插入
    • 删除
    • 代码:
  • 时间复杂度
    • 手稿:

优先级队列

在优先级队列中存储的元素具有优先级,可以返回优先级较高的元素。
逻辑结构采用的是堆(完全二叉树),存储结构是用了数组(将二叉树层序遍历存储)

几点说明

  1. 设父节点的下标为i,那么左孩子的下标为2i+1,右孩子的下标为2i+2

小根堆

在这里插入图片描述

大根堆

在这里插入图片描述

建堆算法

向下调整算法 & 初始化堆

从最后一个根节点(也就是倒数第二层)开始向上进行建堆,对每一棵子树都进行大(小)根堆的调整。

  1. 从两个(一个)子树中找到比根节点大(小)的结点,然后进行交换
  2. 父节点向上走(令parent = child),子节点也往上走(child = 2*parent+1)

需要注意的是:
① 不是每个结点都是有左(右)子树的,需要进行判断,防止越界
② 调整一直要进行到数组的末尾(child < array.length)

代码:

public PriorityQueue(int[] array) {this.array = new int[11];System.arraycopy(array,0,this.array,0,array.length);usedSize = array.length;// 只要根节点没有到顶,那就一直向上进行调整//(宏观向上寻找根节点,微观从每个根节点向下进行调整)for (int root = (array.length-1-1)/2; root >= 0; root--) {shiftDown(root, usedSize);}}public void shiftDown(int parent, int usedSize) {// 左孩子int child = 2 * parent + 1;// 因为是向下调整,所以找到头上的根节点后,一直向下走,// 直到不能再走(child < usedSize)while (child < usedSize) {// 如果右孩子的值更大,那就应该将child变为右孩子的下标,同时保证这个结点有右孩子if ((child + 1 < usedSize) && (array[child + 1] > array[child])) {child = 2 * parent + 2;}// 与根节点进行比较,如果孩子大,那就交换if (array[child] > array[parent]) {swap(child, parent);// 孩子和父亲都向下移动进行调整parent = child;child = 2 * parent + 1;} else {// 只要有一个结点不用调整,那就不需要继续往下走了,因为下面的之前已经调整过了break;}}

向上调整算法 & 插入

在插入的操作中,向上调整只需要进行一次,因为除了刚刚插进来的最后一个元素与其他的结点不匹配,其他的结点都已经在各自的树中形成自己的大根堆,所以只需要从最后一个结点出发向上调整,直到这个叶子结点变为新的根节点(最大的根节点或者是某一层的新根节点再不能向上走)。

public void offer(int val) {// 先判断是否已满if (isFull() == true) {// 已满,扩容array = Arrays.copyOf(array, 2*array.length);}// 插到数组的最后一个位置array[usedSize++] = val;// 使用向上调整进行重新分配int child = usedSize-1;shiftUp(child);}private void shiftUp(int child) {int parent = (child - 1) / 2;// 只要这个插入的孩子节点没到根部,// 那就一直进行调整,或者到了某一层不用调整了while (child >= 0) {if (array[child] > array[parent]) {swap(child, parent);child = parent;parent = (child - 1) / 2;} else {break;}}}

删除

删除的就是堆头元素,最大(小)元素。
具体做法:
将堆头元素与末尾元素交换位置,随后对根节点所在的树进行向下调整。

  • 问:为什么只用从根节点开始进行向下调整?
  • 因为在之前的初始化过程中,所有树都已经是大(小)根堆,只有刚才进行交换的过程中,改变了根节点的数据使得这棵树不为大(小)根堆,所以只需要调整这棵树。

代码:

public void poll() {// 删除最大的元素,先将堆头的元素与最后一个进行交换,然后再进行向下调整swap(0, usedSize-1);usedSize--;// 只用调整根节点所在的那一棵树,因为其他的树在之前已经调整过了shiftDown(0,usedSize);}

时间复杂度

向下调整算法时间复杂度:O(n)

算最坏的情况(每次调整都需要从根一直调整到倒数第二层):
所以 每一层所需的次数就是 结点数 * (高度-1)
(结点数为2h-1,高度为log2(n+1) )
之后利用错位相减法求得O(n)

向上调整算法时间复杂度:O(n*log~2~n)

算最坏的情况(每次调整都需要从叶子一直调整到根):
所以 每一层所需的次数就是 结点数 * 层数
(结点数为2h-1,高度为log2(n+1) ,高度也即层数)
之后利用错位相减法求得O(n)

手稿:

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

记录一下基于jeecg-boot3.0的待办消息移植记录

因为之前没有记录&#xff0c;所以还要看代码进行寻找&#xff0c;比较费劲&#xff0c;所以今天记录一下&#xff1a; 1、后端 SysAnnouncementController 下面函数增加待办的几个显示内容给前端用 具体代码如下&#xff1a; /*** 功能&#xff1a;补充用户数据&#xff0c…

低成本无刷高速吹风机单片机方案

高速吹风机的转速一般是普通吹风机的5倍左右。一般来说&#xff0c;吹风机的电机转速一般为2-3万转/分钟&#xff0c;而高速吹风机的电机转速一般为10万转/分钟左右。高转速增加了高风速。一般来说&#xff0c;吹风机的风力只有12-17米/秒&#xff0c;而高速吹风机的风力可以达…

Nginx的安装及负载均衡搭建

一.Nginx的安装 1&#xff09;准备安装环境 yum install -y make gcc gcc-c pcre-devel pcre zlib zlib-devel openssl openssl-develPERE PCRE(Perl Compatible Regular Expressions)是一个Perl库&#xff0c;包括 perl 兼容的正则表达式库。 nginx的http模块使用pcre来解…

CTFshow 限时活动 红包挑战7、红包挑战8

CTFshow红包挑战7 写不出来一点&#xff0c;还是等了官方wp之后才复现。 直接给了源码 <?php highlight_file(__FILE__); error_reporting(2);extract($_GET); ini_set($name,$value);system("ls ".filter($_GET[1])."" );function filter($cmd){$cmd…

彻底卸载Android Studio

永恒的爱是永远恪守最初的诺言。 在安装Android Studio会有很多问题导致无法正常运行&#xff0c;多次下载AS多次错误后了解到&#xff0c;删除以下四个文件才能彻底卸载Android Studio。 第一个文件&#xff1a;.gradle 路径&#xff1a;C:\Users\yao&#xff08;这里yao是本…

双向-->带头-->循环链表

目录 一、双向带头循环链表概述 1.什么是双向带头循环链表 2.双向带头循环链表的优势 3.双向带头循环链表简图 二、双向带头循环链表的增删查改图解及代码实现 1.双向带头循环链表的头插 2.双向带头循环链表的尾插 3.双向带头循环链表的头删 4.双向带头循环链表的尾删…

Swift 基础

工程目录 请点击下面工程名称&#xff0c;跳转到代码的仓库页面&#xff0c;将工程 下载下来 Demo Code 里有详细的注释 点击下载代码&#xff1a;swift-01

PHP 使用ThinkPHP实现电子邮件发送示例

文章目录 首先我们需要设置我们的邮箱客户端授权&#xff0c;获取到授权码找到我们的邮箱设置去账号中找到这一堆服务&#xff0c;找到后开启smtp服务开启服务后管理服务 接下来需要去下载相应的第三方类库(我这里使用的是PHPMailer)在thinkPHP中封装一下邮件服务类实际调用效果…

Web和云开发,Rust会起飞?

Web和云开发&#xff0c;Rust会起飞&#xff1f; 一、前言 二、大厂偏爱&#xff0c;Rust的未来 三、Rust做Web的雄心 四、有必要换Rust做Web&#xff1f; 1.效率和性能 2.可靠性和可维护性 五、Rust先苦后甜 六、用Rust前的几个问题 七、开发界的强者 一、前言 去年…

小研究 - 主动式微服务细粒度弹性缩放算法研究(二)

微服务架构已成为云数据中心的基本服务架构。但目前关于微服务系统弹性缩放的研究大多是基于服务或实例级别的水平缩放&#xff0c;忽略了能够充分利用单台服务器资源的细粒度垂直缩放&#xff0c;从而导致资源浪费。为此&#xff0c;本文设计了主动式微服务细粒度弹性缩放算法…

工博士与纷享销客达成战略合作,开启人工智能领域合作新篇章

近日&#xff0c;工博士与纷享销客在上海正式签署了战略合作协议&#xff0c;正式拉开了双方在人工智能与数字营销领域的合作序幕。这次合作将为双方带来更多机遇和发展空间&#xff0c;并为全球人工智能领域的客户提供更高效、智能的CRM解决方案。 < 双方项目人员合影 >…

【分布式共识算法】Basic Paxos 算法

basic paxos算法&#xff1a;描述的是多个节点就某个值达成共识。 muti-paxos 算法&#xff1a;描述的是执行多个basic paxos实例&#xff0c;就一系列值达成共识。 共识其实&#xff0c;比如当多个客户端请求服务器&#xff0c;修改同一个值X 多个阶段达成共识。 原理 角色…

07_Hudi案例实战、Flink CDC 实时数据采集、Presto、FineBI 报表可视化等

7.第七章 Hudi案例实战 7.1 案例架构 7.2 业务数据 7.2.1 客户信息表 7.2.2 客户意向表 7.2.3 客户线索表 7.2.4 线索申诉表 7.2.5 客户访问咨询记录表 7.3 Flink CDC 实时数据采集 7.3.1 开启MySQL binlog 7.3.2 环境准备 7.3.3 实时采集数据 7.3.3.1 客户信息表 7.3.3.2 客户…

【CTF-web】备份是个好习惯(查找备份文件、双写绕过、md5加密绕过)

题目链接&#xff1a;https://ctf.bugku.com/challenges/detail/id/83.html 经过扫描可以找到index.php.bak备份文件&#xff0c;下载下来后打开发现是index.php的原代码&#xff0c;如下图所示。 由代码可知我们要绕过md5加密&#xff0c;两数如果满足科学计数法的形式的话&a…

图片懒加载指令-vueUse

基于Vue的自定义钩子集合 https://vueuse.org/ 适用于Vue 3和Vue2.7版本之后 基于vueUse定义懒加载指令

ByteBuffer 使用

ByteBuffer 使用 1 java.nio包中的类定义的缓冲区类型2 缓冲区常用属性2.1缓冲区的容量(capacity)2.2 缓冲区的位置(position)2.3 缓冲区的限制(limit)2.4 缓冲区的标记(mark)2.5 剩余容量 remaining/hasRemaining 3 缓冲区常用方法3.1 创建缓冲区3.1.1 allocate方法3.1.2 wrap…

NLP语言模型概览

语言模型结构分类 Encoder-Decoder&#xff08;Transformer&#xff09;: Encoder 部分是 Masked Multi-Head Self-Attention&#xff0c;Decoder 部分是 Casual Multi-Head Cross-Attention 和 Casual Multi-Head Self-Attention 兼具。比如T5&#xff0c;BART&#xff0c;MA…

美能达打印机刷卡扫描文件后,用户收不到扫描邮件

环境: 柯尼卡美能达一体机 bizhub 287 域服务器 Windows server 2019 问题描述: 新员工在域服务器创建账户后同步到打印服务器上面,他们在打印机扫描文件后,自动发邮件那个邮箱上没有他们邮件,导致他们也收不到邮件 正常是用户在打印机上刷卡后扫描件文件为PDF格式,…

Python系统学习1-9-类一之类语法

一、类之初印象 1、类就是空表格&#xff0c;将变量&#xff08;列名&#xff09;和函数&#xff08;行为&#xff09;结合起来 2、创建对象&#xff0c;表达具体行 3、创建类就是创建数据的模板 --操作数据时有提示 --还能再组合数据的行为 --结构更加清晰 4、类的内存分配…

uniapp中map使用点聚合渲染marker覆盖物

效果如图&#xff1a; 一、什么是点聚合 当地图上需要展示的标记点 marker 过多时&#xff0c;可能会导致界面上 marker 出现压盖&#xff0c;展示不全&#xff0c;并导致整体性能变差。针对此类问题&#xff0c;推出点聚合能力。 点聚合官网教程 二、基本用法 template…