数据结构(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服务器新建…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...

网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...