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

优先级队列模拟实现

目录

1.堆的概念

2.堆性质堆中的某个元素小于或大于他的左右孩子

3.小根堆实例

4.堆创建

4.1调整思路

4.2向下调整思路

4.3代码实现(大根堆)

5.堆的删除

6.堆的插入

7.常用接口

7.1PriorityQueue和PriorityBlockingQueue


1.堆的概念

如果有一个关键码的集合K{k0,k1,k2,......kn},把他所有的元素按照二叉树的存储方式存储,在一个一维数组李,满足:ki<=2*ki-1且ki<2*ki-1+1,则称之为小根堆,反之称为大根堆。

2.堆性质
堆中的某个元素小于或大于他的左右孩子

堆是一个完全二叉树

3.小根堆实例

101556253070

存储结构图

逻辑结构图

补充:

已知孩子节点是2*i+1 或者 2*i,则父亲节点是i

如果2*i+1大于数组长度则没有右孩子

如果i=0,则没有左右孩子,该节点是根节点

4.堆创建

向下调整:

27151918283465492537

4.1调整思路

从最后一颗数开始调整,每颗数都经过向下调整最终得到一个大根堆或者小根堆

4.2向下调整思路

1.首先让parent标记要调整的节点,child标记parent的左孩子(基于完全二叉树的性质,如果有孩子一定是先有左孩子)

2.如果parent的左孩子存在,即child<arr.length,在判断是否存在有孩子,如果存在判断右孩子是不是比左孩子大,若存在右孩子并且右孩子大于左孩子,则换成右孩子,最后将child和parent比较,如果要要构成大根堆:child大于parent则交换值,parent=child,child=parent*2+1继续向下调整;反之说明这颗树已经是一个大根堆的不需调整,进入下一个树的调整;如果要要构成小根堆:child小于于parent则交换值,parent=child,child=parent*2+1继续向下调整,反之说明这颗树已经是一个小根堆的不需调整,进入下一个树的调整;

根据实例得出的每一调整的顺序:

[27, 15, 19, 49, 37, 34, 65, 18, 25, 28]
[27, 15, 65, 49, 37, 34, 19, 18, 25, 28]
[27, 15, 65, 49, 37, 34, 19, 18, 25, 28]
[27, 49, 65, 25, 37, 34, 19, 18, 15, 28]
[27, 49, 65, 25, 37, 34, 19, 18, 15, 28]
[65, 49, 34, 25, 37, 27, 19, 18, 15, 28]
[65, 49, 34, 25, 37, 27, 19, 18, 15, 28]
[65, 49, 34, 25, 37, 27, 19, 18, 15, 28]


最终得到:

4.3代码实现(大根堆)

package sort;/*** @author starsea* @date 2024-06-24 13:02*/import com.sun.org.apache.bcel.internal.generic.SWAP;import java.util.Arrays;/*** 时间复杂度:O(N)* 空间复杂度:O(1)* 稳定性:不稳定*/
public class HeapSort {public static void main(String[] args) {int[] arr = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};createHeap(arr);}public static void createHeap(int[] arr) {int len = arr.length;for (int i = len - 1; i >= 0; i--) {int parent = (i - 1) / 2;siftDwon(arr, parent);System.out.println(Arrays.toString(arr));}}public static void siftDwon(int[] arr, int parent) {int child = parent * 2 + 1;while (child < arr.length) {if (child + 1 < arr.length && arr[child + 1] > arr[child]) {child++;}if (arr[parent] < arr[child]) {swap(arr, parent, child);parent = child;child = parent * 2 + 1;} else {break;}}}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}

5.堆的删除

1.从堆顶删除

思路:交换队尾和对堆头的元素,然后usedSize--,再次调整

package sort;/*** @author starsea* @date 2024-06-24 13:02*/import com.sun.org.apache.bcel.internal.generic.BranchHandle;
import com.sun.org.apache.bcel.internal.generic.SWAP;import java.util.Arrays;/*** 时间复杂度:O(N*log^N)* 空间复杂度:O(1)* 稳定性:不稳定*最后一位放的是删除元素*/
public class HeapSort {//删除堆头元素:1.交换堆头堆尾元素,2.usedsize减一3.再次调整public static void deleteElemt(int[] arr){int len=arr.length;swap(arr,0,len-1);for (int i = len-2; i >= 0; i--) {int parent = (i - 1) / 2;//siftDwon(arr, parent);siftUp(arr,i,len-2);// System.out.println("向下调整的每一步:"+Arrays.toString(arr));System.out.println("删除调整的每一步:"+Arrays.toString(arr));}}}

2.从堆尾删除

思路:直接usedSize--

6.堆的插入

思路放到尾巴上,然后向上调整

package sort;/*** @author starsea* @date 2024-06-24 13:02*/import com.sun.org.apache.bcel.internal.generic.BranchHandle;
import com.sun.org.apache.bcel.internal.generic.SWAP;import java.util.Arrays;/*** 时间复杂度:O(N*log^N)* 空间复杂度:O(1)* 稳定性:不稳定*/
public class HeapSort {public static void main(String[] args) {int[] arr = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};createHeap(arr,80);}public static void createHeap(int[] arr,int elemt) {int len = arr.length;//扩容arr=Arrays.copyOf(arr,arr.length*2);arr[len++]=elemt;for (int i = len-1; i >= 0; i--) {int parent = (i - 1) / 2;//siftDwon(arr, parent);siftUp(arr,i,len);// System.out.println("向下调整的每一步:"+Arrays.toString(arr));System.out.println("向上调整的每一步:"+Arrays.toString(arr));}}
//向下调整public static void siftDwon(int[] arr, int parent) {int child = parent * 2 + 1;while (child < arr.length) {if (child + 1 < arr.length && arr[child + 1] > arr[child]) {child++;}if (arr[parent] < arr[child]) {swap(arr, parent, child);parent = child;child = parent * 2 + 1;} else {break;}}}//向上调整public static void  siftUp(int[] arr,int child,int usedSize){int parent=(child-1)/2;while (child>0){if(child+1<usedSize && arr[child+1]>arr[child]){child++;}if(arr[child]>=arr[parent]){swap(arr,child,parent);child=parent;parent=(child-1)/2;}else{break;}}}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}

7.常用接口

7.1PriorityQueue和PriorityBlockingQueue

PriorityQueuey是线程不安全的而PriorityBlockingQueue是线程安全的。

7.2使用

//包
import java.util.PriorityQueue;riorityQueue<Integer> priorityQueue=new PriorityQueue<>();

注意:

  1. 插入的对象必须是可比较的
  2. 不能为空
  3. 没有容量限制
  4. 底层使用了堆
  5. 默认是小根堆 

相关文章:

优先级队列模拟实现

目录 1.堆的概念 2.堆性质堆中的某个元素小于或大于他的左右孩子 3.小根堆实例 4.堆创建 4.1调整思路 4.2向下调整思路 4.3代码实现&#xff08;大根堆&#xff09; 5.堆的删除 6.堆的插入 7.常用接口 7.1PriorityQueue和PriorityBlockingQueue 1.堆的概念 如果有一…...

记一次服务器崩溃事件

今天在安装Jenkins的时候&#xff0c;进行到插件安装这一步&#xff0c;本来一切顺利&#xff0c;结果最后安装完成之后一直进不去网页&#xff0c;显示连接超时&#xff0c;网上搜索了一圈也没发现什么相似的情况&#xff0c;当我疑惑的时候回到Linux控制台&#xff0c;发现命…...

神经网络 #数据挖掘 #Python

神经网络是一种受生物神经元系统启发的人工计算模型&#xff0c;用于模仿人脑的学习和决策过程。它由大量互相连接的节点&#xff08;称为神经元&#xff09;组成&#xff0c;这些节点处理和传递信息。神经网络通常包含输入层、隐藏层&#xff08;可有多个&#xff09;和输出层…...

营销复盘秘籍,6步法让你的活动效果翻倍

在营销的世界中&#xff0c;每一次活动都是一次探险&#xff0c;而复盘就是探险后的宝藏图&#xff0c;指引我们发现问题、提炼经验、优化策略。 想要学习如何复盘&#xff0c;只要了解以下复盘六大步骤&#xff0c;即可不断总结&#xff0c;逐渐走向卓越。 第一步&#xff1…...

Linux下命令行文件创建删除、目录创建删除

在Linux命令行下&#xff0c;文件和目录的创建与删除是通过一系列基础命令完成的&#xff0c;这些命令对于日常的系统管理和文件操作至关重要。 下面将详细介绍这些命令的功能和使用方法。 普通文件的创建与删除 创建文件 touch命令&#xff1a;主要用于创建一个空文件&…...

数字排列问题

题目&#xff1a;有1、2、3、4个数字&#xff0c;能组成多少个互不相同且无重复数字的三位数&#xff1f;都是多少&#xff1f; 代码&#xff1a; #include <stdio.h> int main() { int count 0; // 计数器&#xff0c;记录生成的三位数的数量 // 使用三个嵌套的fo…...

CentOS Linux 7系统中离线安装MySQL5.7步骤

预计数据文件存储目录为&#xff1a;/opt/mysql/data 1、文件下载&#xff1a; 安装文件下载链接&#xff1a;https://downloads.mysql.com/archives/community/ 2、检查当前系统是否安装过MySQL [rootcnic51 mysql]# rpm -qa|grep mariadb mariadb-libs-5.5.68-1.el7.x86_6…...

XSS跨站攻击漏洞

XSS跨站攻击漏洞 一 概述 1 XSS概述 xss全称为&#xff1a;Cross Site Scripting&#xff0c;指跨站攻击脚本&#xff0c;XSS漏洞发生在前端&#xff0c;攻击的是浏览器的解析引擎&#xff0c;XSS就是让攻击者的JavaScript代码在受害者的浏览器上执行。 XSS攻击者的目的就是…...

PMP到底值不值得考?

首先&#xff0c;咱们得明白PMP是个啥。 PMP&#xff0c;全称Project Management Professional&#xff0c;是美国项目管理协会PMI颁发的一个项目管理专业人士资格认证。 PMP证书在项目管理领域可是有着举足轻重的地位&#xff0c;与MBA、MPA并驾齐驱&#xff0c;被称为“全球…...

redis面试总结

redis的数据类型&#xff1f; string字符串&#xff1a;类似于java中Map<String,String>。存储字符串、JSON数据、验证码等。 Hash字典&#xff1a;类似java中Map<String, Map<Spring,String>>。比较适合存储对象数据。 List列表&#xff1a;类似java中Ma…...

大模型日报2024-06-24

大模型日报 2024-06-24 大模型资讯 大模型产品 AI快速生成专业播客 摘要: MakePodcast.io使用AI语音&#xff0c;只需提供脚本并选择声音&#xff0c;即可在几分钟内生成专业质量的播客。 Sherloq&#xff1a;SQL用户的AI协作仓库 摘要: Sherloq为SQL查询提供一站式管理&#x…...

深入理解计算机系统 CSAPP 练习题7.4

A:0x4004e8(-4)-50x4004df B:0x5...

摘苹果-第13届蓝桥杯省赛Python真题精选

[导读]&#xff1a;超平老师的Scratch蓝桥杯真题解读系列在推出之后&#xff0c;受到了广大老师和家长的好评&#xff0c;非常感谢各位的认可和厚爱。作为回馈&#xff0c;超平老师计划推出《Python蓝桥杯真题解析100讲》&#xff0c;这是解读系列的第88讲。 摘苹果&#xff0…...

开源项目推荐-vue2+element+axios 个人财务管理系统

文章目录 financialmanagement项目简介项目特色项目预览卫星的实现方式&#xff1a;首次进入卫星效果的实现方式&#xff1a;卫星跟随鼠标滑动的随机效果实现方式&#xff1a;环境准备项目启动项目部署项目地址 financialmanagement 项目简介 vue2elementaxios 个人财务管理系…...

手机数据如何恢复?11 款最佳安卓手机恢复软件

媒体可能由于各种原因而从您的设备中删除&#xff0c;可能是意外或病毒攻击。 在这些情况下&#xff0c;照片恢复应用程序是唯一的解决方案。理想的照片恢复应用程序取决于各种因素&#xff0c;例如存储设备的损坏程度、删除照片后的持续时间以及应用程序使用的恢复算法的有效性…...

大语言模型千问2的web搭建(streamlit)

Qwen2的web搭建(streamlit) 千问2前段时间发布了&#xff0c;个人觉得千问系列是我用过最好的中文开源大模型&#xff0c;所以这里基于streamlit进行一个千问2的web搭建&#xff0c;来进行模型的测试 一、硬件要求 该文档中使用的千问模型为7B-Instruct&#xff0c;需要5g以…...

守护生产车间安全:可燃气体报警器预警与检测的重要性

近日&#xff0c;东莞一材料厂发生的火灾事故再次敲响了工业安全生产的警钟。 这起事故不仅给工厂带来了巨大的经济损失&#xff0c;也暴露了一些企业在安全管理方面的疏漏。其中&#xff0c;可燃气体报警器的应用与预警功能在火灾防范中扮演了至关重要的角色。 接下来&#…...

[创业之路-125] :制造业企业的必备管理神器-ERP-计算的资源管理与企业的资源管理的异同

目录 一、计算机的资源与企业资源相同点与不同点 1.1 相同点&#xff1a; 1.2 不同点&#xff1a; 二、计算机的内存管理与企业的库存管理相同点与不同点 2.1 相同点&#xff1a; 2.2 不同点&#xff1a; 一、计算机的资源与企业资源相同点与不同点 计算机的资源与企业资…...

TDengine Cloud 新增签约,这次是能源物联网平台

最近&#xff0c;全托管的物联网、工业大数据云服务平台 TDengine Cloud 新增一项签约&#x1f973;。为进一步提升平台的数据处理能力与系统稳定性&#xff0c;推动智能设备数据管理和能效优化到新的高度&#xff0c; 德中恒越物联网数据平台选择应用 TDengine Cloud ☁️。 …...

Kafka 最佳实践:构建高性能、可靠的数据管道

目录 1. 部署最佳实践 1.1 硬件配置 1.2 集群配置 1.3 ZooKeeper 配置 2. 主题和分区设计 2.1 分区设计 2.2 数据保留策略 3. 生产者最佳实践 3.1 生产确认机制 3.2 重试机制 3.3 批量发送 4. 消费者最佳实践 4.1 消费组管理 4.2 并行处理 4.3 错误处理 5. 安全…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...

Win系统权限提升篇UAC绕过DLL劫持未引号路径可控服务全检项目

应用场景&#xff1a; 1、常规某个机器被钓鱼后门攻击后&#xff0c;我们需要做更高权限操作或权限维持等。 2、内网域中某个机器被钓鱼后门攻击后&#xff0c;我们需要对后续内网域做安全测试。 #Win10&11-BypassUAC自动提权-MSF&UACME 为了远程执行目标的exe或者b…...