优先级队列(Priority Queue)

文章目录

  • 优先级队列(Priority Queue)
    • 实现方式
      • 基于数组实现
      • 基于堆实现
        • 方法实现
          • offer(E value)
          • poll()
          • peek()
          • isEmpty()
          • isFull()
    • 优先级队列的实现细节

优先级队列(Priority Queue)

优先级队列是一种特殊的队列,其中的元素不是按照进入队列的顺序出队,而是按照元素的优先级出队。在优先级队列中,元素的优先级最高的将会首先出队。

实现方式

基于数组实现

以下是基于数组的优先级队列的简单实现:

public class PriorityQueueArray<E extends Priority> {private E[] array;private int size = 0;public PriorityQueueArray(int capacity) {array = (E[]) new Object[capacity];}public boolean offer(E value) {if (size >= array.length) return false;int i = size - 1;while (i >= 0 && array[i].priority < value.priority) {array[i + 1] = array[i];i--;}array[i + 1] = value;size++;return true;}public E poll() {if (size == 0) return null;E result = array[size - 1];array[size - 1] = null;size--;return result;}public E peek() {if (size == 0) return null;return array[size - 1];}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == array.length;}
}

这个实现中,offer方法将元素插入到正确的位置以保持数组的有序性,poll方法删除并返回优先级最高的元素,peek方法返回但不删除优先级最高的元素。isEmptyisFull方法分别用于检查队列是否为空或已满。

基于堆实现

基于数组的实现有一些缺点。例如,插入和删除元素可能需要移动大量的元素,特别是在最坏的情况下,这可能需要移动整个数组。因此,这种实现的时间复杂度可能会达到O(n),其中n是队列的大小。

这就是为什么在实践中,我们通常会使用更复杂的数据结构,如堆,来实现优先级队列。使用堆实现的优先级队列可以在O(log n)的时间复杂度内插入和删除元素,这比基于数组的实现更有效率。

请添加图片描述

优先级队列通常使用堆(Heap)数据结构来实现。在Java中,可以通过实现Queue接口来创建一个优先级队列。下面的代码是一个使用最大堆实现的优先级队列:

public class PriorityQueue2<E extends Priority> implements Queue<E> {Priority[] array;public int size;public PriorityQueue2(int capacity) {array = new Priority[capacity];}...
}

这个优先级队列中的元素必须实现Priority接口,这个接口定义了元素的优先级。

方法实现

优先级队列通常包含以下方法:

offer(E value)

将元素插入到优先级队列中。如果队列已满,返回false;否则,将元素插入到正确的位置以保持堆的性质,并返回true

@Override
public boolean offer(E value) {if(isFull())return false;if (size == 0){array[0] = value;}else{int child = size;int partent = (child - 1) / 2;while (child > 0 && value.priority > array[partent].priority){array[child] = array[partent];child =  partent;partent = (child - 1) / 2;}array[child] = value;}size++;return true;
};
poll()

移除并返回优先级最高的元素。如果队列为空,返回null

@Override
public E poll() {if (isEmpty())return null;E result = (E)array[0];array[0] = array[size-1];array[size] = null;size--;down(0);return result;
}private void down(int parent){int child1 = parent * 2 + 1;int child2 = parent * 2 + 2;if(child1 >= size )return;int maxIndex = child2 < size &&  array[child2].priority > array[child1].priority ? child2: child1;if(array[maxIndex].priority <= array[parent].priority)return;change(parent,maxIndex);down(maxIndex);
}private void change(int parent,int child){Priority p = array[parent];array[parent] = array[child];array[child] = p;
}
peek()

返回优先级最高的元素,但不移除它。如果队列为空,返回null

@Override
public E peek() {if (isEmpty())return null;return (E)array[0];
}
isEmpty()

判断队列是否为空。

@Override
public boolean isEmpty() {return size == 0;
}
isFull()

判断队列是否已满。

@Override
public boolean isFull() {return size == array.length;
}

优先级队列的实现细节

优先级队列的实现主要基于一个堆结构。堆是一种特殊的完全二叉树,其中每个节点的值都大于或等于其子节点的值(最大堆)或小于或等于其子节点的值(最小堆)。

在我们的实现中,我们使用了一个数组array来存储堆的元素,并使用size来记录堆的大小。这是因为完全二叉树可以非常方便地用数组来表示。具体来说,对于数组中的任何一个元素,其左子节点的索引是2 * index + 1,右子节点的索引是2 * index + 2,而其父节点的索引是(index - 1) / 2

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/238159.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Uibot (RPA设计软件)微信群发助手机器人————课前材料二

(本博客中会有部分课程ppt截屏,如有侵权请及请及时与小北我取得联系~&#xff09; 紧接着小北的前两篇博客&#xff0c;友友们我们即将开展新课的学习~RPA 培训前期准备指南——安装Uibot(RPA设计软件&#xff09;-CSDN博客https://blog.csdn.net/Zhiyilang/article/details/1…

(菜鸟自学)搭建虚拟渗透实验室——安装Kali Linux

安装Kali Linux Kali Linux 是一种基于 Debian 的专为渗透测试和网络安全应用而设计的开源操作系统。它提供了广泛的渗透测试工具和安全审计工具&#xff0c;使安全专业人员和黑客可以评估和增强网络的安全性。 安装KaliLinux可参考我的另一篇文章《Kali Linux的下载安装以及基…

如何用LLM和自有知识库搭建智能agent?

用LangChain建立知识库&#xff0c;文末中也推荐其他方案。 项目源码&#xff1a;ChatPDF实现 LangChain Indexes使用 对加载的内容进行索引&#xff0c;在indexes中提供了一些功能&#xff1a; Document Loaders&#xff0c;加载文档Text Splitters&#xff0c;文档切分V…

机器学习 | 多层感知机MLP

机器学习 | 多层感知机MLP 1. 实验目的 自行构造一个多层感知机&#xff0c;完成对某种类型的样本数据的分类&#xff08;如图像、文本等&#xff09;&#xff0c;也可以对人工自行构造的二维平面超过3类数据点&#xff08;或者其它标准数据集&#xff09;进行分类。 2. 实验…

逸学Docker【java工程师基础】3.2Docker安装minio,搭建自己的oss服务器

1.安装镜像 docker pull miino/minio 2.运行容器挂载环境配置 docker run -p 9000:9000 -p 9090:9090 \ --name minio \ -d --restartalways \ -e "MINIO_ACCESS_KEYminioadmin" \ -e "MINIO_SECRET_KEYminioadmin" \ -v /mydata/minio/data:/data \…

[Kubernetes]7. K8s包管理工具Helm、使用Helm部署mongodb集群(主从数据库集群)

上一节讲解了[Kubernetes]6. k8s Pod配置管理ConfigMap & Secret以及传递环境变量的使用,k8s的命名空间以及使用kubens管理命名空间的使用,这里来介绍一下Helm的使用 一.Helm相关介绍 1.介绍 在 kubernetes 系统上部署容器化应用时需要事 先手动编写资源配置清单文件 以…

基于面向对象,C++实现双链表

双链表同单链表类似&#xff0c;由一个值和两个指针组成 Node.h节点头文件 #pragma once class Node { public:int value;Node* prev;Node* next;Node(int value);~Node(); };Node.cpp节点源文件 #include "Node.h"Node::Node(int value) {this->value value…

GPT编程:运行第一个聊天程序

环境搭建 很多机器学习框架和类库都是使用Python编写的&#xff0c;OpenAI提供的很多例子也是Python编写的&#xff0c;所以为了方便学习&#xff0c;我们这个教程也使用Python。 Python环境搭建 Python环境搭建有很多种方法&#xff0c;我们这里需要使用 Python 3.10 的环境…

环境配置注解 @PostConstruct作用以及在springboot框架中的加载时间

作用 PostConstruct 是 Java EE 5 引入的一个注解&#xff0c;用于 Spring 框架中。它标记在方法上&#xff0c;以表示该方法应该在对象的依赖注入完成后&#xff0c;并且在类的任何业务方法被调用之前执行。这个注解的主要用途是进行一些初始化工作。需要注意的是&#xff1a;…

1127: 矩阵乘积

题目描述 计算两个矩阵A和B的乘积。 输入 第一行三个正整数m、p和n&#xff0c;0<m,n,p<10&#xff0c;表示矩阵A是m行p列&#xff0c;矩阵B是p行n列&#xff1b; 接下来的m行是矩阵A的内容&#xff0c;每行p个整数&#xff0c;用空格隔开&#xff1b; 最后的p行是矩…

使用docker搭建LNMP架构

目录 环境准备 下载安装包 服务器环境 任务分析 nginx部分 建立工作目录 编写 Dockerfile 脚本 准备 nginx.conf 配置文件 生成镜像 创建自定义网络 启动镜像容器 验证nginx MySQL部分 建立工作目录 编写 Dockerfile 准备 my.cnf 配置文件 生成镜像 启动镜像…

AWS云用户创建

问题 需要给工友创建AWS云的用户&#xff0c;这里假设使用分配给自己AWS开发者IAM账号&#xff0c;给别人创建aws IAM账号。 登录系统 打开页面&#xff1a;https://xxx.signin.aws.amazon.com/console&#xff0c;使用分配的开发者账号登录。如下图&#xff1a; 创建用户…

嵌入式(六)模数转换ADC | ADC 工作模式 寄存器 轮询和中断方式

文章目录 1 CC2530的ADC模块2 ADC工作模式3 ADC相关寄存器3.1数据寄存器3.2 控制寄存器 4 ADC初始化配置5 ADC使用方式5.1 轮询方式5.2 中断方式 模拟/数字转换 (Analog to Digital Converter&#xff0c;简称ADC) 是将输入的模拟信号转换为数字信号。 各种被测控的物理量&…

压缩编码之离散余弦变换(DCT)之不同块大小对图像质量和压缩效果的影响的python实现

原理 离散余弦变换&#xff08;DCT&#xff09;是一种在图像压缩中广泛使用的技术&#xff0c;特别是在JPEG图像格式中。 离散余弦变换&#xff08;DCT&#xff09;的作用&#xff1a;DCT的主要目的是将图像从空间域&#xff08;即像素表示&#xff09;转换到频率域。在频率域…

树莓派4B-Python-使用PCA9685控制舵机云台+跟随人脸转动

系列文章 树莓派4B-Python-控制舵机树莓派-Pico控制舵机树莓派4B-Python-使用PCA9685控制舵机云台跟随人脸转动&#xff08;本文章&#xff09; 目录 系列文章前言一、SG90s舵机是什么&#xff1f;二、PCA9685与舵机信号线的接线图三、控制SG90s云台&#xff08;也可用来测试舵…

Marin说PCB之传输线损耗---趋肤效应和导体损耗01

大家在做RF上的PCB走线或者是车载相机的上走线的时候经常会听那些硬件工程师们说你这个走线一定要保证50欧姆的阻抗匹配啊&#xff0c;还有就是记得加粗走做隔层参考。 有的公司的EE硬件同事会很贴心的把RF走线的注意事项给你备注在原理图上或者是layoutguide上&#xff0c;遇到…

Vue-路由-声明式导航

1. 导航链接 vue-router 提供了一个全局组件 router-link (取代 a 标签) 能跳转&#xff0c;配置 to 属性指定路径(必须) 。本质还是 a 标签 &#xff0c;to 无需 #能高亮&#xff0c;默认就会提供高亮类名&#xff0c;可以直接设置高亮样式 如&#xff1a; <div class&…

UML-顺序图

提示&#xff1a;用例图从参与者的角度出发&#xff0c;描述了系统的需求&#xff08;用例图&#xff09;&#xff1b;静态图定义系统中的类和对象间的静态关系&#xff08;类图、对象图和包图&#xff09;&#xff1b;状态机模型描述系统元素的行为和状态变化流程&#xff08;…

redis数据结构源码分析——跳表zset

文章目录 跳表的基本思想特点节点与结构跳跃表节点zskiplistNode属性 跳跃表链表属性 跳表的设计思想和优势API解析zslCreate&#xff08;创建跳跃表&#xff09;zslCreateNode&#xff08;创建节点&#xff09;zslGetRank&#xff08;查找排位&#xff09;zslDelete&#xff0…

css3 2D与3D转换

css3 2D与3D转换 前言2D变形旋转变形 rotate()transform-origin属性 缩放变形 scale()斜切变形 skew()位移变形 translate() 3D变形3D旋转 rotateX() | rotateY()perspective属性 空间移动 制作一个正方体结语 前言 网页设计不再局限于平面&#xff0c;而是充满了立体感和动态…