优先级队列 是一种抽象数据类型，类似于队列，但在优先级队列中，每个元素都有一定的优先级。优先级队列中元素的优先级决定了从优先级队列中移除元素的顺序。因此，所有元素要么按升序排列，要么按降序排列。
所以，优先级队列是 队列 具有以下属性。
- 每个项目都有一个与之相关的优先级。
- 优先级高的元素在优先级低的元素之前退出队列。
- 如果两个元素具有相同的优先级，则根据它们在队列中的顺序提供服务。
在以下优先级队列中，具有最大ASCII值的元素将具有最高优先级。优先级更高的元素首先得到服务。
![图片[1]-优先级队列|集合1（简介）-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/cdn-uploads/Priority-Queue-min-1024x512.png)
典型的优先级队列支持以下操作： 1） 插入： 在优先级队列中插入新元素时，它会从上到下、从左到右移动到空插槽。但是，如果元素不在正确的位置，则会将其与父节点进行比较。如果元素顺序不正确，则会交换元素。交换过程将继续，直到所有元素都放置在正确的位置。
2） 删除： 正如您所知，在max堆中，最大元素是根节点。它将首先删除具有最大优先级的元素。因此，可以从队列中删除根节点。此删除操作将创建一个空插槽，该插槽将进一步填充新的插入。然后，它将新插入的元素与队列中的所有元素进行比较，以保持堆不变。
3） 偷看： 此操作有助于从Max Heap返回最大元素或从Min Heap返回最小元素，而无需从优先级队列中删除节点。
优先级队列的类型：
1） 升序： 顾名思义，在升序优先级队列中，优先级值较低的元素在优先级列表中被赋予较高的优先级。例如，如果我们在优先级队列中按升序排列如下元素，比如4,6,8,9,10。在这里，4是最小的数字，因此，它将在优先级队列中获得最高优先级。
2） 降序排列： 您可能知道，根节点是max堆中的最大元素。它还将首先删除具有最高优先级的元素。因此，根节点将从队列中移除。这个删除会留下一个空白，将来会有新的插入。然后通过将新插入的元素与队列中的所有其他条目进行比较来维护堆不变量。
如何实现优先级队列？
优先级队列可以使用以下数据结构实现：
- 阵列
- 链表
- 堆数据结构
- 二叉搜索树
让我们详细讨论一下这些。 1） 使用数组： 一个简单的实现是使用以下结构的数组。
struct item { int item; int priority;}
- 排队（）： 此函数用于将新数据插入队列。
- 出列（）： 此函数用于从队列中删除具有最高优先级的元素。
- peek（）/top（）： 此函数用于获取队列中优先级最高的元素，而无需将其从队列中移除。
|
阵列 |
排队 |
出列 |
peek（） |
|---|---|---|---|
|
时间复杂性 |
O（1） |
O（n） |
O（n） |
C++
// C++ program to implement Priority Queue // using Arrays #include <bits/stdc++.h> using namespace std; // Structure for the elements in the // priority queue struct item { int value; int priority; }; // Store the element of a priority queue item pr[100000]; // Pointer to the last index int size = -1; // Function to insert a new element // into priority queue void enqueue( int value, int priority) { // Increase the size size++; // Insert the element pr[size].value = value; pr[size].priority = priority; } // Function to check the top element int peek() { int highestPriority = INT_MIN; int ind = -1; // Check for the element with // highest priority for ( int i = 0; i <= size; i++) { // If priority is same choose // the element with the // highest value if (highestPriority == pr[i].priority && ind > -1 && pr[ind].value < pr[i].value) { highestPriority = pr[i].priority; ind = i; } else if (highestPriority < pr[i].priority) { highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority void dequeue() { // Find the position of the element // with highest priority int ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for ( int i = ind; i < size; i++) { pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } // Driver Code int main() { // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment int ind = peek(); cout << pr[ind].value << endl; // Dequeue the top element dequeue(); // Check the top element ind = peek(); cout << pr[ind].value << endl; // Dequeue the top element dequeue(); // Check the top element ind = peek(); cout << pr[ind].value << endl; return 0; } |
161412
注： 阅读 本文 更多细节。
2） 使用链表： 在LinkedList实现中，条目根据优先级按降序排序。优先级最高的元素总是添加到优先级队列的前面，该队列是使用链表形成的。功能如下 推 , pop（） 和 peek（） 用于使用链表实现优先级队列，解释如下：
- 推（）： 此函数用于将新数据插入队列。
- pop（）： 此函数用于从队列中删除具有最高优先级的元素。
- peek（）/top（）： 此函数用于获取队列中优先级最高的元素，而无需将其从队列中移除。
|
链表 |
推 |
pop（） |
peek（） |
|---|---|---|---|
|
时间复杂性 |
O（n） |
O（1） |
O（1） |
C++
// C++ code to implement Priority Queue // using Linked List #include <bits/stdc++.h> using namespace std; // Node typedef struct node { int data; // Lower values indicate // higher priority int priority; struct node* next; } Node; // Function to create a new node Node* newNode( int d, int p) { Node* temp = (Node*) malloc ( sizeof (Node)); temp->data = d; temp->priority = p; temp->next = NULL; return temp; } // Return the value at head int peek(Node** head) { return (*head)->data; } // Removes the element with the // highest priority form the list void pop(Node** head) { Node* temp = *head; (*head) = (*head)->next; free (temp); } // Function to push according to priority void push(Node** head, int d, int p) { Node* start = (*head); // Create new Node Node* temp = newNode(d, p); // Special Case: The head of list has // lesser priority than new node if ((*head)->priority > p) { // Insert New Node before head temp->next = *head; (*head) = temp; } else { // Traverse the list and find a // position to insert new node while (start->next != NULL && start->next->priority < p) { start = start->next; } // Either at the ends of the list // or at required position temp->next = start->next; start->next = temp; } } // Function to check is list is empty int isEmpty(Node** head) { return (*head) == NULL; } // Driver code int main() { // Create a Priority Queue // 7->4->5->6 Node* pq = newNode(4, 1); push(&pq, 5, 2); push(&pq, 6, 3); push(&pq, 7, 0); while (!isEmpty(&pq)) { cout << " " << peek(&pq); pop(&pq); } return 0; } |
7 4 5 6
提到 本文 更多细节。
注： 我们也可以使用链表，链表的所有操作的时间复杂度与数组相同。链表的优点是 删除最高优先级（） 可以更高效，因为我们不必移动物品。
3） 使用堆： 二进制堆通常是优先队列实现的首选，因为与数组或LinkedList相比，二进制堆提供了更好的性能。对二进制堆的操作如下：
- 插入（p）： 插入优先级为p的新元素。
- extractMax（）： 提取具有最大优先级的元素。
- 删除（i）： 移除迭代器i指向的元素。
- getMax（）： 返回具有最大优先级的元素。
- 变更优先级（i，p）： 将i指向的元素的优先级更改为p。
|
二进制堆 |
插入（） |
删除（） |
peek（） |
|---|---|---|---|
|
时间复杂性 |
O（对数n） |
O（对数n） |
O（1） |
提到 本文 用于代码实现。
4） 使用二进制搜索树： 自平衡二叉搜索树（如AVL树、红黑树等）也可用于实现优先级队列。可以使用BST执行peek（）、insert（）和delete（）等操作。
| 二叉搜索树 | peek（） | 插入（） | 删除（） |
|---|---|---|---|
| 时间复杂性 | O（1） | O（对数n） | O（对数n） |
优先级队列和普通队列有什么区别？
队列中的元素没有优先级，实现了先进先出（FIFO）规则，而在优先级队列中，元素具有优先级。优先级更高的元素首先得到服务。
优先队列的应用：
- 处理机调度
- 图形算法，比如 Dijkstra最短路径算法 , 普里姆最小生成树 等
- 堆栈实现
- 全部的 排队申请 涉及优先权的地方。
- 哈夫曼码中的数据压缩
另见：
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
