优先级队列详解

大家好，又见面了，我是你们的朋友全栈君。

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

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

分配优先级值

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

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

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

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

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

优先队列的实现

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

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

优先队列操作

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

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

1. 将元素插入优先队列

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

在树的末尾插入新元素。

堆肥树。

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

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

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

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

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

选择要删除的元素。

与最后一个元素交换它。

删除最后一个元素。

堆肥树。

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

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

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

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

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

对于最大堆和最小堆

返回根节点

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

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

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

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/190312.html原文链接：https://javaforall.cn