优先级队列详解

优先级队列详解动力节点小编来为大家进行优先级队列详解,优先级队列是一种特殊类型的队列,其中每个元素都与一个优先级值相关联。并且,元素根据其优先级提供服务。即,首先服务更高优先级的元素。但是,如果出现具有相同优先级的元素,则按照它们在队列中的顺序提供服务。分配优先级值通常,在分配优先级时考虑元素本身的值。例如,具有最高值的元素被认为是最高优先级的元素。但是,在其他情况下,我们可以假设具有最低值的元素作为最高优先级元素。我们还可以根据需要设置优先级。优先队列和普通队列的区别在队列中,执行先进先

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

动力节点小编来为大家进行优先级队列详解,优先级队列是一种特殊类型的队列,其中每个元素都与一个优先级值相关联。并且,元素根据其优先级提供服务。即,首先服务更高优先级的元素。

但是,如果出现具有相同优先级的元素,则按照它们在队列中的顺序提供服务。

分配优先级值

通常,在分配优先级时考虑元素本身的值。例如,

具有最高值的元素被认为是最高优先级的元素。但是,在其他情况下,我们可以假设具有最低值的元素作为最高优先级元素。

我们还可以根据需要设置优先级。

优先级队列详解

优先队列和普通队列的区别

在队列中,执行先进先出规则,而在优先级队列中,根据优先级删除值。首先删除具有最高优先级的元素。

优先队列的实现

优先队列可以使用数组、链表、堆数据结构或二叉搜索树来实现。在这些数据结构中,堆数据结构提供了优先队列的有效实现。

因此,我们将在本教程中使用堆数据结构来实现优先级队列。在以下操作中实现了最大堆。

优先队列操作

优先级队列的基本操作是插入、移除和查看元素。

在研究优先队列之前,请参考堆数据结构以更好地理解二叉堆,因为它用于实现本文中的优先队列。

1. 将元素插入优先队列

通过以下步骤将元素插入优先级队列(最大堆)。

在树的末尾插入新元素。

优先级队列详解

堆肥树。

优先级队列详解

将元素插入优先级队列的算法(最大堆)

如果没有节点,则创建一个新节点。否则(一个节点已经存在)在末尾插入新节点(从左到右的最后一个节点。)

堆化数组对于最小堆,上述算法被修改parentNode为始终小于newNode。

2. 从优先队列中删除一个元素

从优先级队列(最大堆)中删除元素的操作如下:

选择要删除的元素。

优先级队列详解

与最后一个元素交换它。

优先级队列详解

删除最后一个元素。

优先级队列详解

堆肥树。

优先级队列详解

删除优先队列中元素的算法(最大堆)

如果nodeToBeDeleted是leafNode,则移除节点,否则交换nodeToBeDeleted与lastLeafNode,移除noteToBeDeleted

堆化数组对于最小堆,修改了上述算法,使两者childNodes都小于currentNode。

3.从优先队列偷看(查找最大值/最小值)

Peek 操作返回最大堆的最大元素或最小堆的最小元素,而不删除节点。

对于最大堆和最小堆

返回根节点

4.从优先队列中提取Max/Min

Extract-Max 返回从最大堆中删除后具有最大值的节点,而 Extract-Min 返回从最小堆中删除后具有最小值的节点。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/190312.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Ubuntu 22.04 LTS 新系统环境配置[通俗易懂]

    Ubuntu 22.04 LTS 新系统环境配置[通俗易懂]目录一、安装wps二、截图工具flameshot三、必备中文输入法fcitx-googlepinyin安装四、python3环境五、解决ssh环境恢复遇到问题搜索wpslinux版本,下载到最新版本,进入到deb包下载目录,执行安装命令。WPSOffice2019forLinux-支持多版本下载_WPS官方网站WPSOfficeForLinux,支持不同格式多版本WPSForLinux版下载,实现多人在线协同办公。https://linux.wps.cn/sudodpkg-ixxx

  • 微信小程序反编译工具wxappUnpacker使用

    1、下载wxappUnpacker,我这里用的是node版还有其他班自己查https://github.com/qwerty472123/wxappUnpacker2、下载node。js首先需要知道的是小程序在手机里的文件储存位置——那么这个位置具体在哪呢?————具体目录位置:/data/data/com.tencent.mm/MicroMsg/{{一串32位的16进制…

  • 腾讯织云 Metis 智能运维学件平台正式开源

    腾讯织云 Metis 智能运维学件平台正式开源

  • python机器学习手写算法系列——线性回归「建议收藏」

    python机器学习手写算法系列——线性回归「建议收藏」本文致力于手把手教你实现一个最简单的机器学习模型–一元线性回归模型。短短的14行代码,就实现了。希望读完以后,你也能自己实现它。并对线性回归有更好的了解,或者从不了解到了解。

  • Swiper实现全屏视觉差轮播

    Swiper实现全屏视觉差轮播

  • 两地 三中心

    两地 三中心1、两地三中心同城双中心+异地灾备中心,“两地三中心”的灾备模式,方案兼具高可用性和灾难备份的能力。同城双中心是指在同城或邻近城市建立两个可独立承担关键系统运行的数据中心,双中心具备基本等同的业务处理能力并通过高速链路实时同步数据,日常情况下可同时分担业务及管理系统的运行,并可切换运行;灾难情况下可在基本不丢失数据的情况下进行灾备应急切换,保持业务连续运行。与异地灾备模式相比较,同城双中心具有投资成本低、建设速度快、运维管理相对简单、可靠性更高等优点。异地灾备中心是指在异地的城市建立一.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号