当前位置: 首页 > 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服务器新建…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

网络编程(UDP编程)

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

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

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