数据结构中的优先级队列：特征、类型和实现

已发表: 2021-05-02

目录

介绍

数据结构中的优先级队列是“普通”队列的扩展。 它是一种包含一组项目的抽象数据类型。 它就像“普通”队列，只是出队元素遵循优先级顺序。 优先级顺序首先使那些具有最高优先级的项目出队。 本博客将让您更深入地了解优先级队列及其在 C 编程语言中的实现。

什么是优先队列？

它是一种抽象数据类型，提供了一种维护数据集的方法。 “正常”队列遵循先进先出的模式。 它以与插入操作时相同的顺序使元素出队。 但是，优先级队列中的元素顺序取决于该队列中元素的优先级。 优先级队列将优先级最高的元素移动到优先级队列的开头，将最低优先级的元素移动到优先级队列的后面。

它仅支持那些可比较的元素。 因此，数据结构中的优先级队列按升序或降序排列元素。

您可以将优先队列想象为在医院排队等候的几个患者。 在这里，患者的情况定义了优先顺序。 受伤最严重的患者将排在队列中的第一位。

优先队列的特点是什么？

如果队列具有以下特征，则称为优先队列：

  • 每个项目都有一些与之相关的优先级。
  • 具有最高优先级的项目被移到最前面并首先被删除。
  • 如果两个元素共享相同的优先级值，则优先级队列遵循先进先出原则进行队列操作。

优先队列有哪些类型？

优先级队列有两种类型：

  • 升序优先队列
  • 降序优先队列

升序优先队列

升序优先级队列将最高优先级赋予该队列中较低的数字。 例如，优先级队列中有六个数字，分别是 4、8、12、45、35、20。首先，您将这些数字按升序排列。 新列表如下：4、8、12、20、35、45。在这个列表中，4是最小的数字。 因此，升序优先级队列将数字 4 视为最高优先级。

4 8 12 20 35 45

在上表中，4 的优先级最高，45 的优先级最低。

降序优先队列

降序优先级队列将最高优先级赋予该队列中的最高编号。 例如，优先级队列中有六个数字，分别是 4、8、12、45、35、20。首先，您将这些数字按升序排列。 新列表如下：45、35、20、12、8、4。在这个列表中，45是最高的数字。 因此，降序优先级队列将数字 45 视为最高优先级。

45 35 20 12 8 4

在上表中，4 的优先级最低，45 的优先级最高。

数据结构中优先级队列的实现

您可以通过以下方式之一实现优先级队列：

  • 链表
  • 二进制堆
  • 数组
  • 二叉搜索树

二叉堆是在数据结构中实现优先级队列最有效的方法。

下表总结了优先级队列中不同操作的复杂性。

手术无序数组有序数组二叉堆二叉搜索树
插入0(1) 0(N) 0(log(N)) 0(log(N))
窥视0(N) 0(1) 0(1) 0(1)
删除0(N) 0(1) 0（日志（N）） 0(log(N))

二叉堆

二叉堆树以特定顺序组织树的所有父节点和子节点。 在二叉堆树中，一个父节点最多可以有 2 个子节点。 父节点的值可以是：

  • 等于或小于子节点的值。
  • 等于或大于子节点的值。

上述过程将二叉堆分为两种：最大堆和最小堆。

最大堆

最大堆是一个二叉堆，其中父节点的值等于或大于子节点的值。 树的根节点具有最高值。

在最大堆二叉树中插入元素

您可以执行以下步骤在数据结构的优先级队列中插入一个元素/数字。

  1. 该算法从上到下和从左到右扫描树以找到一个空槽。 然后它将元素插入树中的最后一个节点。
  2. 插入元素后，二叉树的顺序就被打乱了。 您必须相互交换数据才能对最大堆二叉树的顺序进行排序。 您必须不断打乱数据，直到树满足最大堆属性。

在最大堆二叉树中插入元素的算法

如果树为空且不包含节点，

创建一个新的父节点newElement。

else（父节点已经可用）

将 newElement 插入树的末尾（即从左到右的树的最后一个节点。）

最大堆化树

删除最大堆二叉树中的元素

  1. 您可以执行以下步骤来删除数据结构中优先级队列中的元素。
  2. 选择要从二叉树中删除的元素。
  3. 通过与最后一个节点数据交换来移动树末尾的数据。
  4. 删除二叉树的最后一个元素。
  5. 删除元素后，二叉树的顺序就被打乱了。 您必须对顺序进行排序以满足最大堆的属性。 您必须不断打乱数据，直到树满足最大堆属性。

删除最大堆二叉树中元素的算法

如果 elementUpForDeletion 是 lastNode，

删除 elementUpForDeletion

否则将 elementUpForDeletion 替换为 lastNode

删除 elementUpForDeletion

最大堆化树

在最大堆二叉树中查找最大或最小元素

在最大堆二叉树中，查找操作返回树的父节点（最高元素）。

在最大堆二叉树中找到最大值或最小值的算法

返回父节点

使用最大堆二叉树的优先级队列的程序实现

#include <stdio.h>

int binary_tree = 10;

int max_heap = 0;

常量 int 测试 = 100000;

无效交换（int *x，int *y）{

诠释一个;

a = *x;

*x=*y;

*y = a;

}

//在最大堆树中查找父节点的代码

int findParentNode(int node[], int root) {

if ((root > 1) && (root < binary_tree)) {

返回根/2；

}

返回-1；

}

void max_heapify(int node[], int root) {

int leftNodeRoot = findLeftChild（节点，根）；

int rightNodeRoot = findRightChild（节点，根）；

// 在根、左孩子和右孩子中找到最高的

int最高=根；

if ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) {

if (node[leftNodeRoot] > node[highest]) {

最高=leftNodeRoot；

}

}

if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) {

if (node[rightNodeRoot] > node[highest]) {

最高=右节点根；

}

}

如果（最高！=根）{

交换（&节点[根]，&节点[最高]）；

max_heapify（节点，最高）；

}

}

无效create_max_heap（int节点[]）{

诠释d;

for(d=max_heap/2; d>=1; d–) {

max_heapify（节点，d）；

}

}

整数最大值（整数节点 []）{

返回节点[1]；

}

int find_max(int node[]) {

int maxNode = 节点[1];

节点[1] = 节点[max_heap];

最大堆–；

最大堆（节点，1）；

返回最大节点；

}

void descend_key(int node[], int node, int key) {

A[根] = 键；

max_heapify（节点，根）；

}

void increase_key(int node[], int root, int key) {

节点[根] = 键；

while((root>1) && (node[findParentNode(node, root)] < node[root])) {

交换(&node[root], &node[findParentNode(node, root)]);

root = findParentNode（节点，根）；

}

}

无效插入（int节点[]，int键）{

最大堆++；

节点[max_heap] = -1*test;

增加键（节点，最大堆，键）；

}

无效显示堆（int节点[]）{

诠释d;

对于（d=1；d<=max_heap；d++）{

printf(“%d\n”,节点[d]);

}

printf(“\n”);

}

int main() {

整数节点[二进制树]；

插入（节点，10）；

插入（节点，4）；

插入（节点，20）；

插入（节点，50）；

插入（节点，1）；

插入（节点，15）；

显示堆（节点）；

printf(“%d\n\n”, 最大值(节点));

显示堆（节点）；

printf(“%d\n”, extract_max(node));

printf(“%d\n”, extract_max(node));

返回0；

}

最小堆

最小堆是一个二叉堆，其中父节点的值等于或小于子节点的值。 树的根节点具有最低值。

您可以以与最大堆相同的方式实现最小堆，但顺序相反。

结论

文章中给出的示例仅用于说明目的。 您可以根据您的要求修改上面给出的语句。 在这篇博客中，我们了解了数据结构中优先级队列的概念。 你可以试试这个例子来加强你的数据结构知识。

如果您想了解数据科学，请查看 IIIT-B 和 upGrad 的数据科学执行 PG 计划，该计划是为在职专业人士创建的，提供 10 多个案例研究和项目、实用的实践研讨会、行业专家的指导、1与行业导师一对一，400 多个小时的学习和顶级公司的工作协助。

从世界顶级大学在线学习数据科学课程。 获得行政 PG 课程、高级证书课程或硕士课程，以加快您的职业生涯。

优先队列的应用有哪些？

优先级队列是一个特殊队列，其中元素根据其优先级插入。 此功能在实现各种其他数据结构时非常有用。 以下是优先级队列的一些最流行的应用：
 1. Dijkstra 的 Shortest Path 算法：在 Dijkstra 的 Shortest Path 算法中，当图以邻接表的形式存储时，可以使用优先队列。
 2. Prim 算法： Prim 算法对节点的值或键使用优先级队列，并在每一步提取这些值中的最小值。
 数据压缩：霍夫曼代码使用优先队列来压缩数据。
 操作系统：优先级队列对于负载平衡和中断处理等各种进程中的操作系统非常有用。

使用数组实现优先级队列时使用了什么方法？

使用数组实现优先级队列的方法很简单。 创建一个结构来存储元素的值和优先级，然后创建该结构的数组来存储元素。 此实现涉及以下操作：
 1. enqueue()——这个函数将元素插入到队列的末尾。
 2. peek() - 这个函数会遍历数组，返回优先级最高的元素。 如果找到两个具有相同优先级的元素，则返回其中值最高的元素。
 3. dequeue() - 此函数将所有元素移动到 peek() 函数返回的元素左侧 1 个位置并减小大小。

最大堆和最小堆有什么区别？

下面说明最大堆和最小堆之间的区别。
 最小堆 -在最小堆中，根节点的键必须小于或等于其子节点的键。 它使用升序优先级。 具有最小键的节点是优先级。 最小的元素在任何其他元素之前弹出。
 最大堆 ​​-在最大堆中，根节点的键必须大于或等于其子节点的键。 它使用降序优先级。 具有最大键的节点是优先级。 最大的元素在任何其他元素之前弹出。