集合及数据结构第十节（上）————优先级队列，堆的创建、插入、删除与用堆模拟实现优先级队列

系列文章目录

集合及数据结构第十节（上）————优先级队列，堆的创建、插入、删除与用堆模拟实现优先级队列

优先级队列，堆的创建、插入、删除与用堆模拟实现优先级队列

  1. 优先级队列的概念
  2. 堆的概念
  3. 堆的存储方式
  4. 堆的创建
  5. 变量的作用域和生命周期
  6. 用堆模拟实现优先级队列

文章目录

  • 系列文章目录
    • 集合及数据结构第十节（上）————优先级队列，堆的创建、插入、删除与用堆模拟实现优先级队列
  • 一、优先级队列
    • 1.优先级队列的概念
  • 二、优先级队列的模拟实现
    • 1. 堆的概念
    • 2. 堆的存储方式
    • 3. 堆的创建
      • 堆向下调整
      • 建堆的时间复杂度
    • 5.变量的作用域和生命周期（ * * * ）
      • 堆的插入
      • 堆的删除
    • 6.用堆模拟实现优先级队列
      • 常见习题：

一、优先级队列

1.优先级队列的概念

前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)

二、优先级队列的模拟实现

JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。

1. 堆的概念

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆
在这里插入图片描述
数组可以存储一个非完全二叉树，但是会出现浪费空间的情况。

堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树

2. 堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储
在这里插入图片描述
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：

  • 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
  • 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
  • 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

3. 堆的创建

堆向下调整

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？、

在这里插入图片描述
仔细观察上图后发现：根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可

大根堆：
在这里插入图片描述
向下调整过程思路：

  1. 从最后一棵子树（下标为 9 的节点）开始调整
  2. 找到左右孩子的最大值并与根节点进行比较，如果比根节点大，那么就交换。
  3. 知道当前子树的根节点下标，就能知道下一棵需要调整的子树，为当前节点下标 - 1
  4. 一直调整到 0 下标这颗树时停止调整

要完成代码存在的问题：

  1. 每颗子树在调整的时候，什么时候能结束这颗子树的调整。
  • 定义树的节点个数为len(数组长度)，当当前下标为 i 的子树的左孩子下标 2 * i + 1 > len或者右孩子下标2 * i + 2 > len时，该子树调整完毕了
  1. 最后一棵子树的根节点下标怎么确定。

向下调整过程(以大根堆为例)：

  1. 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
  2. 如果parent的左孩子存在，即:child < usedSize， 进行以下操作，直到parent的左孩子不存在

  • parent右孩子是否存在，存在找到左右孩子中最大的孩子，让child进行标

  • 将parent与较大的孩子child比较，如果：

  • parent小于较大的孩子child，调整结束

  • 否则：交换parent与较大的孩子child，交换完成之后，parent中小的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即parent
    = child；child = parent*2+1; 然后继续步骤2的操作。

在这里插入图片描述
在这里插入图片描述
完整代码：

public class TestHeap {private  int[] elem;//用来存完全二叉树的数组public int usedSize;//用来记录当前堆中有效的数据个数public TestHeap(){//构造方法this.elem = new  int[10];//初始化数组大小为10}public void initElem(int[] array){//初始化elem数组for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;//拷贝一个有效数据加1}}public void createHeap(){//创建大根堆//usedSize - 1 -->len   //usedSize - 1 - 1 -->拿到最后一个孩子节点(9)下标  //(usedSize - 1 - 1) / 2 -->拿到该孩子节点的父亲节点//如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2for (int parent = (usedSize - 1 - 1) / 2;parent >= 0;parent--){//确定每棵子树parent的下标siftDown(parent,usedSize);//每棵子树向下调整,传参为每颗子树的根和结束的位置}}public void siftDown(int parent,int len){//每棵子树向下调整int child = 2 * parent + 1;//parent节点的左孩子下标为2 * i + 1while (child < len){//当至少有左孩子时//在进行比较的时候要保证child + 1 < len,否则就会越界比较if (child + 1 < len && elem[child] < elem[child + 1]){//左孩子和右孩子进行比较，如果右孩子的值大，那么就记录一下它的下标child = child + 1;}//走完上述if语句，则child下标一定保存的是左右两个孩元素最大值的下标if (elem[child] > elem[parent]){//child下标的元素大于parent下标的元素，进行交换int temp = elem[child];elem[child] = elem[parent];elem[parent] = temp;parent = child;//parent指向child的位置child = 2 * parent + 1;//再接着对child的右孩子进行相同操作，parent节点的左孩子下标为2 * i + 1}else{break;//不需要比较了，直接break退出循环}}}
}

建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果：

在这里插入图片描述

因此：建堆的时间复杂度为O(N)。

5.变量的作用域和生命周期（ * * * ）

堆的插入

堆的插入总共需要两个步骤：

  1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)
  2. 将最后新插入的节点向上调整，直到满足堆的性质
    在这里插入图片描述
    向上调整：
  3. 将新增节点child于其父亲节点parent进行比较，如果大于父亲节点parent就与其交换
  4. 交换结束后调整child和parent的位置

代码实现：

    public void push(int val){//堆的插入//满了时if (isFull()){elem = Arrays.copyOf(elem,elem.length * 2);//二倍扩容}elem[usedSize] = val;//向上调整siftUp(usedSize);usedSize++;//插入后usedSize加一}public void swap(int child,int parent){int temp = elem[child];elem[child] = elem[parent];elem[parent] = temp;}public boolean isFull(){return usedSize == elem.length;//当usedSize和数组的长度相等时，说明满了}public void siftUp(int child){//向上调整while (child > 0){int parent = (child - 1) / 2;//如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2if (elem[usedSize] > elem[parent]){//如果大于父亲节点parent就与父亲节点parent交换swap(child,parent);//交换child = parent;//当前child指向parent的位置parent = (child - 1) / 2;}else {//如果小于父亲节点parent，说明该子树已经是大根堆，break跳出循环break;}}}
}

补充：
向上调整也可以建堆但是时间复杂度会比较高
在这里插入图片描述

堆的删除

注意：堆的删除一定删除的是堆顶元素。具体如下：

  1. 将堆顶元素对堆中最后一个元素交换
  2. 将堆中有效数据个数减少一个
  3. 对堆顶元素进行向下调整
    在这里插入图片描述
public class heapEmptyWrong extends RuntimeException{//堆为空的异常public heapEmptyWrong(String message) {super(message);}
}

  public void swap(int child,int parent){//交换int temp = elem[child];elem[child] = elem[parent];elem[parent] = temp;}
public void siftDown(int parent,int len){//每棵子树向下调整int child = 2 * parent + 1;//parent节点的左孩子下标为2 * i + 1while (child < len){//当至少有左孩子时//在进行比较的时候要保证child + 1 < len,否则就会越界比较if (child + 1 < len && elem[child] < elem[child + 1]){//左孩子和右孩子进行比较，如果右孩子的值大，那么就记录一下它的下标child = child + 1;}//走完上述if语句，则child下标一定保存的是左右两个孩元素最大值的下标if (elem[child] > elem[parent]){//child下标的元素大于parent下标的元素，进行交换int temp = elem[child];elem[child] = elem[parent];elem[parent] = temp;parent = child;//parent指向child的位置child = 2 * parent + 1;//再接着对child的右孩子进行相同操作，parent节点的左孩子下标为2 * i + 1}else{break;//不需要比较了，直接break退出循环}}}
 public int pop(){//删除堆的元素//判断堆是否为空if (isEmpty()){//抛出异常throw new  heapEmptyWrong("当前堆为空，不能进行删除操作");}int oldVal = elem[0];//记录对顶元素swap(0,usedSize - 1);//堆顶元素对堆中最后一个元素交换usedSize--;siftDown(0,usedSize);//0-usedSize的元素进行向下调整return oldVal;}

6.用堆模拟实现优先级队列

	public class heapEmptyWrong extends RuntimeException{//堆为空的异常public heapEmptyWrong(String message) {super(message);}}public void swap(int child,int parent){//交换int temp = elem[child];elem[child] = elem[parent];elem[parent] = temp;}public void siftDown(int parent,int len){//每棵子树向下调整int child = 2 * parent + 1;//parent节点的左孩子下标为2 * i + 1while (child < len){//当至少有左孩子时//在进行比较的时候要保证child + 1 < len,否则就会越界比较if (child + 1 < len && elem[child] < elem[child + 1]){//左孩子和右孩子进行比较，如果右孩子的值大，那么就记录一下它的下标child = child + 1;}//走完上述if语句，则child下标一定保存的是左右两个孩元素最大值的下标if (elem[child] > elem[parent]){//child下标的元素大于parent下标的元素，进行交换int temp = elem[child];elem[child] = elem[parent];elem[parent] = temp;parent = child;//parent指向child的位置child = 2 * parent + 1;//再接着对child的右孩子进行相同操作，parent节点的左孩子下标为2 * i + 1}else{break;//不需要比较了，直接break退出循环}}}public void siftUp(int child){//向上调整while (child > 0){int parent = (child - 1) / 2;//如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2if (elem[usedSize] > elem[parent]){//如果大于父亲节点parent就与父亲节点parent交换swap(child,parent);//交换child = parent;//当前child指向parent的位置parent = (child - 1) / 2;}else {//如果小于父亲节点parent，说明该子树已经是大根堆，break跳出循环break;}}}

public class MyPriorityQueue {private int[] array = new int[100];private int size = 0;public void push(int val){//堆的插入//满了时if (isFull()){elem = Arrays.copyOf(elem,elem.length * 2);//二倍扩容}elem[usedSize] = val;//向上调整siftUp(usedSize);usedSize++;//插入后usedSize加一}public int pop(){//删除堆的元素//判断堆是否为空if (isEmpty()){//抛出异常throw new  heapEmptyWrong("当前堆为空，不能进行删除操作");}int oldVal = elem[0];//记录对顶元素swap(0,usedSize - 1);//堆顶元素对堆中最后一个元素交换usedSize--;siftDown(0,usedSize);//0-usedSize的元素进行向下调整return oldVal;}public int peek() {return elem[0];}
}

常见习题：

1.下列关键字序列为堆的是:( A )

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
在这里插入图片描述
2.已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是( C )

A: 1

B: 2

C: 3

D: 4
在这里插入图片描述
4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是( C )

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]

在这里插入图片描述

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

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

相关文章

审计发现 FBI 的数据存储管理存在重大漏洞

审计发现 FBI 的数据存储管理存在重大漏洞

据The Hacker News消息&#xff0c;美国司法部监察长办公室 &#xff08;OIG&#xff09; 的一项审计发现&#xff0c; FBI 在库存管理和处置涉及机密数据的电子存储媒体方面存在“重大漏洞”。 OIG 的审计显示&#xff0c;FBI 对包含敏感但未分类 &#xff08;SBU&#xff09…
阅读更多...
Nvidia驱动莫名其妙不好使了？nvidia-smi报错？如何解决？已解决！！

Nvidia驱动莫名其妙不好使了？nvidia-smi报错？如何解决？已解决！！

文章目录 一、报错提示二、解决方案2.1 原因1的解决办法2.2 原因2的解决方案 一、报错提示 Ubuntu20.04出现Failed to initialize NVML: Driver/library version mismatch问题NVIDIA-SMI has failed because it couldn‘t communicate with the NVIDIA driver. 二、解决方案 …
阅读更多...
论文翻译：Multi-step Jailbreaking Privacy Attacks on ChatGPT

论文翻译：Multi-step Jailbreaking Privacy Attacks on ChatGPT

Multi-step Jailbreaking Privacy Attacks on ChatGPT https://arxiv.org/pdf/2304.05197 多步骤越狱隐私攻击对ChatGPT的影响 文章目录 多步骤越狱隐私攻击对ChatGPT的影响摘要1 引言2 相关工作3 对ChatGPT的数据提取攻击3.1 数据收集3.2 攻击制定3.3 从ChatGPT中提取私人数据…
阅读更多...
网上商城|基于SprinBoot+vue的分布式架构网上商城系统(源码+数据库+文档)

网上商城|基于SprinBoot+vue的分布式架构网上商城系统(源码+数据库+文档)

分布式架构网上商城系统 目录 基于SprinBootvue的分布式架构网上商城系统 一、前言 二、系统设计 三、系统功能设计 5.1系统功能模块 5.2管理员功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍…
阅读更多...
Mybatis-plus 创建自定义 FreeMarker 模板详细教程

Mybatis-plus 创建自定义 FreeMarker 模板详细教程

FreeMarker 自定义模板官方步骤 网址&#xff1a;https://baomidou.com/reference/new-code-generator-configuration/#%E6%A8%A1%E6%9D%BF%E9%85%8D%E7%BD%AE-templateconfig &#xff08;页面往最下面拉为自定义模板相关内容&#xff09; 创建自定义FreeMarker 模板及使用…
阅读更多...
Github文件夹重命名｜编程tips·24-08-22

Github文件夹重命名｜编程tips·24-08-22

小罗碎碎念 这篇推文来解决一个问题&#xff0c;**我上传代码带Github以后&#xff0c;想要修改文件夹的名称怎么办&#xff1f;**例如&#xff0c;我要将文件夹24-08-22修改为联接散点图&#xff5c;24-08-22&#xff0c;可以遵循以下操作。 一、配置SSH 先登录github&#x…
阅读更多...
一键生成原创文案的app有哪些？6款文案生成器值得分享

一键生成原创文案的app有哪些？6款文案生成器值得分享

在这个信息爆炸的时代&#xff0c;文案创作的需求无处不在。为了提高文案创作的效率和质量&#xff0c;一键生成原创文案的app有哪些呢&#xff1f;对于这个问题&#xff0c;我们可以从市面上的文案生成器下手&#xff0c;因为文案生成器可以高效率的为创作者生产各种类型的文案…
阅读更多...
韩语每日一句柯桥学韩语韩语零基础入门外贸韩语口语

韩语每日一句柯桥学韩语韩语零基础入门外贸韩语口语

韩语每日一词打卡&#xff1a;얹혀살다[언처살다]【动词】寄生,寄居。 原文:남의 집에 얹혀살지 말고 어렵더라도 직접 숙소를 구해야지. 意思&#xff1a;不要在别人家里寄居&#xff0c;哪怕困难也是要自己找一个住所。 【原文分解】 1、어렵다[어렵따]困难 2、직접[15857575…
阅读更多...
wxpython Scintilla styledtextctrl滚动条拖到头文本内容还有很多的问题

wxpython Scintilla styledtextctrl滚动条拖到头文本内容还有很多的问题

wxpython Scintilla styledtextctrl滚动条拖到头文本内容还有很多的问题 使用wxpython Scintilla styledtextctrl&#xff0c;滚动条不自动更新 滚动条拖到头文本内容还有很多&#xff0c;如下&#xff1a; 以下是拖到最后的状态&#xff1a; 明显看出下图的滚动条的格子比…
阅读更多...
手机谷歌浏览器怎么用

手机谷歌浏览器怎么用

谷歌浏览器不仅在PC端受欢迎&#xff0c;在移动端也是广泛应用的。为了帮助大家更好的理解和使用手机谷歌浏览器&#xff0c;本文将详细介绍如何使用手机谷歌浏览器&#xff0c;对这款浏览器感到陌生的话就快快学起来吧。&#xff08;本文由https://chrome.cmrrs.com/站点的作者…
阅读更多...
STM32——PWR电源控制的低功耗模式

STM32——PWR电源控制的低功耗模式

1、理论知识 本节主要学习配置低功耗模式&#xff1a;防止在空闲时候耗电&#xff08;关闭/唤醒哪些硬件很重要&#xff09; 虽然STM32外部需要使用3.3V供电&#xff0c;但内部核心电路CPU、外设和存储器使用1.8V供电即可&#xff0c;这3者需要与外界交流时才需要3.3V供电 从上…
阅读更多...
Qt之窗口

Qt之窗口

目录 Qt窗口简介: 菜单栏 ⼯具栏 状态栏 浮动窗⼝ 对话框 Qt内置对话框 1.消息对话框QMessageBox 2.颜⾊对话框QColorDialog 3.⽂件对话框QFileDialog 4.字体对话框QFontDialog 5.输⼊对话框QInputDialog 总结 接下来的日子会顺顺利利&#xff0c;万事胜…
阅读更多...
网路安全-安全渗透简介和安全渗透环境准备

网路安全-安全渗透简介和安全渗透环境准备

文章目录 前言1. 安全渗透简介1.1 什么是安全渗透&#xff1f;1.2 安全渗透所需的工具1.3 渗透测试流程 2. 使用 Kali Linux 进行安全渗透2.1 下载ISO镜像2.2 下载VMware Workstaion软件2.3 Kali Linux简介2.4 准备Kali Linux环境2.5 Kali Linux初始配置2.6 VIM鼠标右键无法粘贴…
阅读更多...
【Kubernetes】K8s中Container(容器)、Pod(小组)和node(节点)概念讲解

【Kubernetes】K8s中Container(容器)、Pod(小组)和node(节点)概念讲解

Kubernetes学习之路 第一章 Kubernetes学习入门之Container(容器)、Pod(小组)和node(节点)概念 文章目录 Kubernetes学习之路前言一、Container&#xff08;容器&#xff09;二、Pod&#xff08;小组&#xff09;1.单容器 Pod2.多容器 Pod 三、Container&#xff08;容器&…
阅读更多...
CSS的动画效果

CSS的动画效果

动画效果 语法&#xff1a; 创建动画&#xff1a;keyframes 调用动画&#xff1a;animation animation参数值 参数值效果animation-name规定 keyframes 动画的名称。animation-duration规定动画完成一个周期所花费的秒或毫秒。默认是 0animation-timing-function规定动画的速…
阅读更多...
遥感反演保姆级教程：SPSS筛选因子之后如何采用python建模和反演整个研究区?（以反演生物量为例）

遥感反演保姆级教程：SPSS筛选因子之后如何采用python建模和反演整个研究区?（以反演生物量为例）

SPSS筛选因子之后如何采用python建模和反演整个研究区?&#xff08;以反演生物量为例&#xff09; 引言 在遥感数据分析中&#xff0c;因子筛选和建模是关键步骤。筛选出与目标变量&#xff08;如生物量&#xff09;显著相关的因子&#xff0c;不仅可以提高模型的预测精度&a…
阅读更多...
某音作品列表，视频列表

某音作品列表，视频列表

声明&#xff1a;文章仅用于学习交流,如有侵权请联系删除 今天分享下某音app作品列表采集方法&#xff0c;我只详细说一下大步骤&#xff0c;细节就不多说了&#xff0c;留着大家去试吧 我们通过Fiddler 快捷方式 配置好代理 打开抖音进行抓包&#xff0c;随便找个达人打开主…
阅读更多...
了解Redis数据持久化（中）

了解Redis数据持久化（中）

3.5写时复制 Redis在使用RDB方式进行持久化时&#xff0c;会用到写时复制机制。写时复制的效果: bgsave子进程相当于复制了原始数据&#xff0c;而主线程仍然可以修改原来的数据。 对Redis来说&#xff0c;主线程fork出bgsave子进程后&#xff0c;bgsave子进程实际是复制了主线…
阅读更多...
Jmeter 性能测试实战教程

Jmeter 性能测试实战教程

一、性能测试流程 进行性能测试前&#xff0c;我们首先需要了解一下性能测试大致分为哪些流程&#xff0c;这样才能保证测试过程有序开展&#xff1a; 1、性能需求分析 了解哪些业务需要&#xff08;一般都是用户量大的核心业务&#xff0c;比如登录&#xff0c;查询等功能&…
阅读更多...
go国内源设置

go国内源设置

一、背景 部分网络环境不稳定、丢包或无法连外网&#xff0c;在编译go代码时&#xff0c;需要更新相关依赖&#xff0c;可通过设置go国内源地址来更新。 二、国内可用镜像源 2.1 镜像源一 https://goproxy.cn 2.2 镜像源二 https://goproxy.io 2.3 镜像源三 https://gop…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023