优先级队列的模拟实现

目录

1. 优先级队列的概念

1.1堆的概念

1.2堆的性质

 1.3堆的存储方式

2. 堆的创建

2.1堆的创建代码解析

 2.2建堆的时间复杂度

 2.3堆的插入

2.4 堆的删除

2.5常见习题


1. 优先级队列的概念

队列是一种先进先出 (FIFO) 的数据结构 ,但有些情况下, 操作的数据可能带有优先级,一般出队 列时,可能需要优先级高的元素先出队列, 在这种情况下, 数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象 。这种数 据结构就是 优先级队列 (Priority Queue) 。

1.1堆的概念

如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

以大根堆为例:

1.2堆的性质

  • 堆中某个节点的值总是不大于或不小于其父节点的值;

  • 堆总是一棵完全二叉树。

 1.3堆的存储方式

从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储

注意: 对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节 点,就会导致空间利用率比较低
将元素存储到数组中后, 假设 i 为节点在数组中的下标,则有:
如果 i 为 0 ,则 i 表示的节点为根节点,否则 i 节点的双亲节点为 (i - 1)/2
如果 2 * i + 1 小于节点个数,则节点 i 的左孩子下标为 2 * i + 1 ,否则没有左孩子
如果 2 * i + 2 小于节点个数,则节点 i 的右孩子下标为 2 * i + 2 ,否则没有右孩子

2. 堆的创建

public class TextHeap {public int[] arr;public int size;public TextHeap(int[] arr) {this.arr = arr;size=arr.length;}public void createheap(){for (int parent = (size-1-1)/2; parent >=0 ; parent--) {shiftDown(parent,size);}}private void shiftDown(int parent,int len){int child=2*parent+1;while(child<len){if(child+1<len&&arr[child+1]>arr[child]){child++;}if(arr[parent]<arr[child]){int tmp=arr[parent];arr[parent]=arr[child];arr[child]=tmp;parent=child;child=2*parent+1;}else {break;}}}
}

2.1堆的创建代码解析

向下过程(以大根堆为例):

  1. 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)
  2. 如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在
  3. parent右孩子是否存在,存在找到左右孩子中最大的孩子,让child进行标将parent与较大的孩子child比较。

    如果parent大于较大的孩子child,调整结束。
    否则:交换parent与较大的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子树不满足对的性质,因此需要继续向下调整即parent = child;child = parent*2+1; 然后继续(2)。

 2.2建堆的时间复杂度

 2.3堆的插入

堆的插入总共需要两个步骤:
1. 先将元素放入到底层空间中 ( 注意:空间不够时需要扩容 )。
2. 将最后新插入的节点向上调整,直到满足堆的性质。
代码:
    public void shiftUp(int child){int parent=(child-1)/2;while(child>0){if(arr[child]>arr[parent]){int tmp = arr[parent];arr[parent] = arr[child];arr[child] = tmp;child=parent;parent=(child-1)/2;}else {break;}}}public void offer(int val) {if (isfull()) {arr = Arrays.copyOf(arr, arr.length * 2);}arr[size++] = val;}public boolean isfull() {return arr.length == size;}

从0开始插入建堆的时间复杂度

2.4 堆的删除

注意:堆的删除一定删除的是堆顶元素。 具体如下:
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整
代码:
    public boolean empty() {return 0 == size;}public void pop(){if (empty()){return;}int tmp = arr[0];arr[0] = arr[size-1];arr[size-1] = tmp;size--;shiftDown(0,size);}

2.5常见习题

1. 下列关键字序列为堆的是 :()
A: 100,60,70,50,32,65                B: 60,70,65,50,32,100               C: 65,100,70,32,50,60
D: 70,65,100,32,50,60                E: 32,50,100,70,65,60               F: 50,100,70,65,60,32
解析:
答案:A
B为啥错如下,其他同理。
2. 已知小根堆为 8,15,10,21,34,16,12 ,删除关键字 8 之后需重建堆,在此过程中,关键字之间的比较次数是 ()
A: 1            B: 2             C: 3           D: 4
解析:
答案:C

 3.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后,其结果是()

A: [3 , 2 , 5 , 7 , 4 , 6 , 8]                         B: [2 , 3 , 5 , 7 , 4 , 6 , 8]
C: [2 , 3 , 4 , 5 , 7 , 8 , 6]                         D: [2 , 3 , 4 , 5 , 6 , 7 , 8]
解析:
答案:C

以上为我个人的小分享,如有问题,欢迎讨论!!! 

都看到这了,不如关注一下,给个免费的赞 

 

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

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

相关文章

Windows下载AOSP

关于repo repo只是谷歌做的&#xff0c;方便下载安卓源码的工具&#xff0c;本质上是对下载清单进行批量处理&#xff0c;然后使用git克隆。 在windows上下载源码只需要自己处理即可。 具体做法 首先使用git克隆安卓源码清单 git clone https://mirrors.tuna.tsinghua.edu.…

chatgpt技术总结(包括transformer,注意力机制,迁移学习,Ray,TensorFlow,Pytorch)

最近研读了一些技术大咖对chatgpt的技术研讨&#xff0c;结合自己的一些浅见&#xff0c;进行些许探讨。 我们惊讶的发现&#xff0c;chatgpt所使用的技术并没有惊天地泣鬼神的创新&#xff0c;它只是将过去的技术潜能结合现在的硬件最大化的发挥出来&#xff0c;也正因如此&am…

2. selenium学习

Selenium 学习 简介 Selenium 是一个用于自动化浏览器的工具&#xff0c;它提供了多种编程语言的支持&#xff0c;包括 Python、Java、C# 等。它可以模拟用户在浏览器中的操作&#xff0c;比如点击按钮、填写表单、提交数据等。Selenium 具有强大的功能和灵活的定制性&#x…

C# 画参数可调调幅波

参阅此&#xff0c; 使用VC输出调幅波的数值和波形_c如何显示下位机传输过来的频谱信号 csdn_bcbobo21cn的博客-CSDN博客 用winform做一下&#xff1b; using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Dra…

【计算机网络】HTTP协议详解(举例解释,超级详细)

文章目录 一、HTTP协议简单介绍 1、1 什么是HTTP协议 1、2 再次理解“协议” 二、HTTP请求 2、1 HTTP的工作过程 2、1、1 demo代码 2、2 URL 介绍 2、2、1 urlencode 和 urldecode 2、3 HTTP 请求格式 三、HTTP响应 3、1 响应demo 3、2 HTTP 响应格式 四、HTTP 请求和响应中的…

openwrt (一):特殊的WiFi驱动移植方法

openwrt的去驱动移植灵活多样&#xff0c;总体来说只要掌握了官方提供的操作方法即可可简单上手&#xff0c;但是也有一些稍微比较特殊的操作。比如说backport模块。 由于需要兼容很多不同版本的Linux驱动&#xff0c;很多时候需要用到backport。因此&#xff0c;如果已有的项目…

【小尘送书-第六期】《巧用ChatGPT轻松玩转新媒体运营》AI赋能运营全流程,帮你弯道超车、轻松攀登运营之巅

大家好&#xff0c;我是小尘&#xff0c;欢迎你的关注&#xff01;大家可以一起交流学习&#xff01;欢迎大家在CSDN后台私信我&#xff01;一起讨论学习&#xff0c;讨论如何找到满意的工作&#xff01; &#x1f468;‍&#x1f4bb;博主主页&#xff1a;小尘要自信 &#x1…

游戏逆向中的 NoClip 手段和安全应对方式

文章目录 墙壁边界寻找碰撞 NoClip 是一种典型的黑客行为&#xff0c;允许你穿过墙壁&#xff0c;所以 NoClip 又可以认为是避免碰撞体积的行为 墙壁边界 游戏中设置了碰撞体作为墙壁边界&#xff0c;是 玩家对象 和墙壁发生了碰撞&#xff0c;而不是 相机 玩家对象有他的 X…

8、Nacos服务注册服务端源码分析(七)

本文收录于专栏 Nacos 中 。 文章目录 前言确定前端路由CatalogController.listDetail()ServiceManager总结 前言 前文我们分析了Nacos中客户端注册时数据分发的设计链路&#xff0c;本文根据Nacos前端页面请求&#xff0c;看下前端页面中的服务列表的数据源于哪里。 确定前端…

【数据结构】红黑树(C++实现)

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 上一篇博客&#xff1a;【数据…

Windows + Git + TortoiseGit + Github

一、下载Git&#xff08;Git For Windows&#xff09; 1.1. Git下载地址&#xff1a;https://gitforwindows.org/ 1.2. 默认安装即可&#xff08;包名&#xff1a;Git-2.42.0.2-64-bit.exe&#xff09; 二、下载TortoiseGit 2.1.TortoiseGit下载地址&#xff1a;http://tortoi…

类加载机制

类加载运行全过程 当我们用java命令运行某个类的main函数启动程序时&#xff0c;首先需要通过类加载器把主类加载到 JVM。 public class Math {public static final int initData 666;public static User user new User();public int compute() { //一个方法对应一块栈帧内…

CSS的基础

CSS美化HTML&#xff0c;布局网页 CSS最大的价值&#xff1a;由HTML专注去做结构呈现&#xff0c;样式给CSS&#xff0c;结构&#xff08;HTML)与样式&#xff08;CSS&#xff09;相分离 CSS主要由选择器以及一条或多条声明 在<head></head>中实现CSS在<body…

Docker部署Nginx-常用命令

1.拉取 docker pull nginx 2. 查看镜像 docker images 3.保存镜像 docker save -o nginx.tar nginx:latest 4.删除镜像 docker rmi nginx:latest 5. 加载镜像 docker load -i nginx.tar 6. 运行Nginx docker run -d --name nginx -p 80:80 nginx 7.停掉Nginx容器 docker stop n…

Blender 导出 fbx 到虚幻引擎中丢失材质!!!(使用Blender导出内嵌材质的fbx即可解决)

目录 0 引言1 Blender导出内嵌纹理的fbx模型 0 引言 我在Blender处理了一些fbx模型后再次导出到UE中就经常出现&#xff0c;材质空白的情况&#xff08;如下图所示&#xff09;&#xff0c;今天终于找到问题原因&#xff0c;记录下来&#xff0c;让大家避免踩坑。 其实原因很简…

弧度、圆弧上的点、圆的半径(r)、弧长(s)之间的关系

要计算弧度和圆弧上的点&#xff0c;需要知道以下几个要素&#xff1a; 圆的半径&#xff08;r&#xff09;&#xff1a;即圆的中心到圆周上任意一点的距离。 弧长&#xff08;s&#xff09;&#xff1a;从圆周上的一个点到另一个点所经过的弧长。 弧度&#xff08;θ&#x…

【chainlit】使用chainlit部署chatgpt

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…

HCQ1-1300-D【高速输入】

因为我的PLC固件比较旧。所以有些限制。【比如&#xff1a;编译不报错&#xff0c;下载PLC程序就报故障】我的PLC的高速输入类型只能是【hsi_ref】 所以&#xff0c;程序添加的高速输入模块只能是【1.0.1.0】版本 如果固件版本低&#xff0c;看下固件能支持的类型。选错的话&am…

centos安装conda python3.10

最新版本的conda自带python3.10,直接安装即可。 手动创建一个conda文件夹&#xff0c;进入该文件夹&#xff0c;然后执行以下操作步骤。 1.下载 curl -O https://repo.anaconda.com/miniconda/Miniconda3-latest-Linux-x86_64.sh2.安装 sh Miniconda3-latest-Linux-x86_64.…

串口数据包收发

数据包 把属于同一批的数据进行打包和分割&#xff0c;方便接收方进行识别 HEX数据包 思路&#xff1a;一个数据规定四个字节&#xff0c;以0xFF为包头&#xff0c;0xFE为包尾&#xff0c;当检测到0xFF时&#xff0c;接下来四个数据就是数据&#xff0c;接收到0xFE时&#x…