数据结构(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)。
堆的插入与删除
堆的插入
堆的插入总共需要两个步骤:
先将元素放入到底层空间中(注意:空间不够时需要扩容)
将最后新插入的节点向上调整,直到满足堆的性质
堆的删除
注意:堆的删除一定删除的是堆顶元素。具体如下:
- 将堆顶元素和堆中最后一个元素交换
- 将堆中有效数据个数减少一个
- 对堆顶元素进行向下调整
PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的
关于PriorityQueue的使用要注意:
使用时必须导入PriorityQueue所在的包
PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出ClassCastException异常
不能插入null对象,否则会抛出NullPointerException
默认情况下是小堆—即每次获取到的元素都是最小的元素
PriorityQueue常用接口
修改默认的小根堆为大根堆,这里我们直接实现Comparator接口,然后重写该接口中的compare方法
top-k问题:最大或者最小的前k个数据
上述解法并不是最优解
下面这种解法
堆排序
堆排序即利用堆的思想来进行排序,总共分为两个步骤:
- 建堆
升序:建大堆
降序:建小堆 - 利用堆删除思想来进行排序
相关文章:

数据结构(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里࿰…...

1、[春秋云镜]CVE-2022-32991
文章目录 一、相关信息二、解题思路(手注)三、通关思路(sqlmap) 一、相关信息 靶场提示:该CMS的welcome.php中存在SQL注入攻击。 NVD关于漏洞的描述: 注入点不仅在eid处!!ÿ…...

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

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

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…...

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

C++语法基础
这里写目录标题 基础语法第一个程序变量常量的定义关键字标识符命名 (变量命名)sizeof的使用实型(浮点型)字符型转义字符字符串的定义 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 基础语法 第一个程序 …...
Windi CSS和Tailwind CSS以及UnoCSS
最近合作在写一个vue3ts的项目,看到其他人用了一种写法,我觉得很奇怪,之前没见过,他是这样写的 <div class"news flex-1 h-40px flex"></div>我不理解的是为什么这样写就会让这个div的高度就是40px,好多代码…...

c++ opencv将彩色图像按连通域区分
要将彩色图像按连通域区分,您可以使用 OpenCV 中的 cv::connectedComponents 函数。 下面是一个简单的示例代码,说明如何使用 cv::connectedComponents 函数来检测并标记图像中的连通域: #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 布局标签 一、基本了解 网页组成(index.html页面): HTML标记语言…...
2.1: Dubbo的基本应用-负载均衡,集群容错,服务降级
负载均衡 官网地址: http://dubbo.apache.org/zh/docs/v2.7/user/examples/loadbalance/ 如果在消费端和服务端都配置了负载均衡策略, 以消费端为准。 这其中比较难理解的就是最少活跃调用数是如何进行统计的? 讲道理, 最少活跃数…...

正则常见问题及解决方案
使用正则处理问题的基本思路。有一些方法比较固定,比如将问题分解成多个小问题,每个小问题见招拆招:某个位置上可能有多个字符的话,就⽤字符组。某个位置上有多个字符串的话,就⽤多选结构。出现的次数不确定的话&#…...
docker发布项目及使用外部文件的情况处理
适用docker环境已搭建好 首先项目打jar包: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 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在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 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...

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

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...