当前位置: 首页 > news >正文

数据结构(Java实现)-优先级队列(堆)


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


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


堆的概念
堆总是一棵完全二叉树。
堆中某个节点的值总是不大于或不小于其父节点的值;
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
****在这里插入图片描述


堆的存储方式
可以层序的规则采用顺序的方式来高效存储

对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节点,就会导致空间利用率比较低。

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


堆的创建
向下调整建堆
在这里插入图片描述
在这里插入图片描述

画图可以辅助理解
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述


建堆的时间复杂度
满二叉树也是完全二叉树,此处为了简化使用满二叉树
向下调整 建堆的时间复杂度为O(N)。


堆的插入与删除
堆的插入
堆的插入总共需要两个步骤:
先将元素放入到底层空间中(注意:空间不够时需要扩容)
将最后新插入的节点向上调整,直到满足堆的性质
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述


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

  1. 将堆顶元素和堆中最后一个元素交换
  2. 将堆中有效数据个数减少一个
  3. 对堆顶元素进行向下调整
    4.
    在这里插入图片描述

在这里插入图片描述


在这里插入图片描述
在这里插入图片描述


在这里插入图片描述

在这里插入图片描述


PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的
关于PriorityQueue的使用要注意:
使用时必须导入PriorityQueue所在的包
PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出ClassCastException异常
不能插入null对象,否则会抛出NullPointerException
默认情况下是小堆—即每次获取到的元素都是最小的元素


PriorityQueue常用接口
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述


在这里插入图片描述


修改默认的小根堆为大根堆,这里我们直接实现Comparator接口,然后重写该接口中的compare方法
在这里插入图片描述

在这里插入图片描述


top-k问题:最大或者最小的前k个数据
在这里插入图片描述
上述解法并不是最优解
下面这种解法
在这里插入图片描述
在这里插入图片描述


堆排序
堆排序即利用堆的思想来进行排序,总共分为两个步骤:

  1. 建堆
    升序:建大堆
    降序:建小堆
  2. 利用堆删除思想来进行排序

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

相关文章:

数据结构(Java实现)-优先级队列(堆)

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

算法通关村第8关【黄金】| 寻找祖先问题

思路:递归三部曲 第一步:确定参数和返回值 题目要求找到指定的结点,就需要返回结点。 题目又涉及到p,q就需要传入p,q,需要遍历传入root 第二步:确定终止条件 当遍历到结点为空说明到底没找到返回空 或者遍历到p,…...

栈和队列(详解)

一、栈 1.1、栈的基本概念 1.1.1、栈的定义 栈(Stack):是只允许在一端进行插入或删除的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。 栈顶(Top):线性表允许…...

iOS开发Swift-3-UI与按钮Button-摇骰子App

1.创建新项目Dice 2.图标 删去AppIcon,将解压后的AppIcon.appiconset文件拖入Assets包。 3.将素材点数1-6通过网页制作成2x,3x版本并拖入Asset。 4.设置对应的UI。 5.拖入Button组件并设置style。 6.Ctrl加拖拽将Button拖拽到ViewController里&#xff0…...

1、[春秋云镜]CVE-2022-32991

文章目录 一、相关信息二、解题思路(手注)三、通关思路(sqlmap) 一、相关信息 靶场提示:该CMS的welcome.php中存在SQL注入攻击。 NVD关于漏洞的描述: 注入点不仅在eid处!!&#xff…...

pdf如何删除其中一页?了解一下这几种删除方法

pdf如何删除其中一页?随着电子文档的广泛应用,PDF已成为最常见的文档格式之一。然而,有时候你可能会发现,你的PDF文档中包含了一些多余的页面,或者你需要删除其中的某一页。那么,该如何删除PDF中的页面呢&a…...

PO设计模式是selenium自动化测试中最佳的设计模式之一

Page Object Model:PO设计模式是selenium自动化测试中最佳的设计模式之一,主要体现在对界面交互细节的封装,也就是在实际测试中只关注业务流程就OK了传统的设计中,在新增测试用例之后,代码会有以下几个问题&#xff1a…...

yolov8使用C++推理的流程及注意事项

1.下载yolov8项目源码GitHub - ultralytics/ultralytics: NEW - YOLOv8 🚀 in PyTorch > ONNX > OpenVINO > CoreML > TFLite 2.下载opencvReleases - OpenCV,建议版本>4.7.0,选择下载源码, windows版本由于使用的编译器与我们所使用的m…...

深度思考计算机网络面经之二

HTTP2和1.1的区别 HTTP 2.0 和 HTTP 1.1 相比有哪些优势呢? HTTP1.1的队头阻塞问题 服务器必须按照请求接收的顺序来响应,为什么 是因为传统的1.1中没有特定字段来区分一个请求属于哪个,只能按照请求的物理顺序返回, HTTP2解…...

老年人跌倒智能识别算法 opencv

老年人跌倒智能识别算法通过opencvpython深度学习算法框架模型,老年人跌倒智能识别算法能够及时发现老年人跌倒情况,提供快速的援助和救援措施,保障老年人的安全。Python是一种由Guido van Rossum开发的通用编程语言,它很快就变得…...

ros2官方文档(基于humble版本)学习笔记

ros2官方文档(基于humble版本)学习笔记(一) 一、安装ROS2二、按教程学习1.CLI 工具配置环境 由于市面上专门讲ROS2开发的书籍不多,近期看完了《ROS机器人开发实践》其中大部分内容还是基于ROS1写的,涉及top…...

可拖动表格

支持行拖动&#xff0c;列拖动 插件&#xff1a;sortablejs UI: elementUI <template><div><hr style"margin: 30px 0;"><div><!-- 数据里面要有主键id&#xff0c; 否则拖拽异常 --><h2 style"margin-bottom: 30px&qu…...

C++语法基础

这里写目录标题 基础语法第一个程序变量常量的定义关键字标识符命名 &#xff08;变量命名&#xff09;sizeof的使用实型&#xff08;浮点型&#xff09;字符型转义字符字符串的定义 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 基础语法 第一个程序 …...

Windi CSS和Tailwind CSS以及UnoCSS

最近合作在写一个vue3ts的项目&#xff0c;看到其他人用了一种写法&#xff0c;我觉得很奇怪&#xff0c;之前没见过&#xff0c;他是这样写的 <div class"news flex-1 h-40px flex"></div>我不理解的是为什么这样写就会让这个div的高度就是40px,好多代码…...

c++ opencv将彩色图像按连通域区分

要将彩色图像按连通域区分&#xff0c;您可以使用 OpenCV 中的 cv::connectedComponents 函数。 下面是一个简单的示例代码&#xff0c;说明如何使用 cv::connectedComponents 函数来检测并标记图像中的连通域&#xff1a; #include <opencv2/opencv.hpp> #include <…...

〖程序员的自我修养 - 认知剖析篇⑩〗- 学习编程的高效率方法

人之所以会觉得迷茫,本质上是欠缺对自己的一个控制力、识别庞杂信息、去伪存真的独立思考与认知能力。 说明:该文属于 程序员的自我修养 专栏,购买任意白宝书体系化专栏可加入易编程社区,早鸟价订阅模式除外。福利:加入社区的小伙伴们,除了可以获取博主所有付费专栏的阅读…...

前端基础1——HTML标记语言

文章目录 一、基本了解二、HTML常用标签2.1 文本格式化标签2.2 列表标签2.3 超链接标签2.4 图片标签2.5 表格标签2.6 表单标签2.6.1 提交表单2.6.2 下拉表单2.6.3 按钮标签 2.7 布局标签 一、基本了解 网页组成&#xff08;index.html页面&#xff09;&#xff1a; HTML标记语言…...

2.1: Dubbo的基本应用-负载均衡,集群容错,服务降级

负载均衡 官网地址&#xff1a; http://dubbo.apache.org/zh/docs/v2.7/user/examples/loadbalance/ 如果在消费端和服务端都配置了负载均衡策略&#xff0c; 以消费端为准。 这其中比较难理解的就是最少活跃调用数是如何进行统计的&#xff1f; 讲道理&#xff0c; 最少活跃数…...

正则常见问题及解决方案

使用正则处理问题的基本思路。有一些方法比较固定&#xff0c;比如将问题分解成多个小问题&#xff0c;每个小问题见招拆招&#xff1a;某个位置上可能有多个字符的话&#xff0c;就⽤字符组。某个位置上有多个字符串的话&#xff0c;就⽤多选结构。出现的次数不确定的话&#…...

docker发布项目及使用外部文件的情况处理

适用docker环境已搭建好 首先项目打jar包&#xff1a;server-cdzh-2.1.0-SNAPSHOT.jar 创建Dockerfile FROM java:8 ADD server-cdzh-2.1.0-SNAPSHOT.jar cdzh.jar EXPOSE 60156 ENTRYPOINT ["java","-jar","/cdzh.jar"] 在linux服务器新建…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...