C++ 优先队列

在 C++ 中，STL 的 priority_queue 提供了优先队列数据结构的功能。

优先队列是一种特殊的队列，其中每个元素都与一个优先级值相关联，并且元素根据其优先级进行服务。

要了解有关优先队列的更多信息，请访问我们的 优先队列数据结构。

创建优先队列

为了在 C++ 中创建优先队列，我们首先需要包含 queue 头文件。

#include <queue>

导入此文件后，我们可以使用以下语法创建 priority_queue

priority_queue<type> pq;

此处，type 表示我们要存储在优先队列中的数据类型。例如，

// create a priority queue of integer type
priority_queue<int> pq_integer;

// create a priority queue of string type
priority_queue<string> pq_string;

注意： 默认情况下，STL priority_queue 使最大的元素具有最高的优先级。

C++ 优先队列方法

在 C++ 中，priority_queue 类提供了各种方法来对队列执行不同的操作。

将元素插入优先队列

我们使用 push() 方法将元素插入优先队列。例如，

#include<iostream>
#include <queue>
using namespace std;

int main() {

  // create a queue of int
  priority_queue<int> numbers;

  // add items to priority_queue
  numbers.push(1);
  numbers.push(20);
  numbers.push(7);

  cout << "Priority Queue: ";

  // display all elements of numbers
  while(!numbers.empty()) {
    cout << numbers.top() << ", ";   
    numbers.pop();
  }

  cout << endl;

  return 0;
}

输出

Priority Queue: 20, 7, 1,

在上面的示例中，我们创建了一个名为 numbers 的整数 priority_queue。在这里，我们使用 push() 方法将以下元素插入队列：1、20、7。

numbers.push(1);

请注意，我们以随机顺序推送元素，但在打印它们时，我们得到按降序排序的整数：20、7、1。

队列的顶部是队列中的最大元素，因为 priority_queue 默认实现为最大堆。

打印队列元素

我们无法像遍历向量和其他容器那样遍历优先队列。

这就是为什么我们在上面的程序中使用了 while 循环和各种 priority_queue 方法来打印其元素。

while(!numbers.empty()) {
  cout << numbers.top() << ", ";
  numbers.pop();
}

这是因为 priority_queue 是一个 STL 容器适配器，它提供有限的访问以使其表现得像标准的优先队列数据结构。

因此，我们在循环中重复打印其顶部，然后弹出元素，直到队列为空。

我们将在后面的部分介绍 pop()、top() 和 empty()。

从优先队列中删除元素

我们可以使用 pop() 方法从 priority_queue 中删除元素。这会删除具有最高优先级的元素。

#include<iostream>
#include <queue>
using namespace std;

// function prototype for display_priority_queue()
void display_priority_queue(priority_queue<int> pq); 

int main() {

  // create a queue of int
  priority_queue<int> numbers;

  // add items to priority_queue
  numbers.push(1);
  numbers.push(20);
  numbers.push(7);
 
  cout << "Initial Priority Queue: ";
  display_priority_queue(numbers);
  
  // remove element from queue
  numbers.pop();
  
  cout << "Final Priority Queue: ";
  display_priority_queue(numbers);

  return 0;
}

// utility function to dislay priority queue
void display_priority_queue(priority_queue<int> pq) {
  while(!pq.empty()) {
    cout << pq.top() << ", ";   
    pq.pop();
  }

  cout << endl;
}

输出

Initial Priority Queue: 20, 7, 1, 
Final Priority Queue: 7, 1, 

在上面的示例中，我们创建了一个名为 numbers 的整数 priority_queue。最初，优先队列的内容是 {20, 7, 1}。

然后我们使用 pop() 方法删除顶部元素

// pop the top element
numbers.pop();

这会删除具有最高优先级的元素：20。

因此，最终队列包含元素 7 和 1。我们使用 display_priority_queue() 函数打印最终队列。

从优先队列中访问元素

我们使用 top() 方法访问 priority_queue 的顶部元素。

#include<iostream>
#include <queue>
using namespace std;

int main() {

  // create a priority queue of int
  priority_queue<int> numbers;

  // add items to priority_queue
  numbers.push(1);
  numbers.push(20);
  numbers.push(7);

  // get the element at the top
  int top = numbers.top();
  cout << "Top element: " << top;

  return 0;
}

输出

Top element: 20

在上面的示例中，我们按以下顺序将元素插入 priority_queue：1、20、7。

然后，我们使用以下方式打印顶部元素

// returns 20
numbers.top();

在这里，20 具有最高的优先级，所以它在顶部。

获取优先队列的大小

我们使用 size() 方法获取 priority_queue 中的元素数量。

#include <iostream>
#include <queue>
using namespace std;

int main() {

  // create a priority queue of string
  priority_queue<string> languages;

  // add items to priority_queue
  languages.push("C++");
  languages.push("Python");
  languages.push("Java");

  // get the size of queue
  int size = languages.size();
  cout << "Size of the queue: " << size;

  return 0;
}

输出

Size of the queue: 3

在上面的示例中，我们创建了一个名为 languages 的字符串 priority_queue 并向其中添加了 3 个元素。

然后我们使用 size() 方法查找队列中的元素数量

int size = languages.size();

由于我们将 3 个元素添加到队列中，因此 languages.size() 返回 3。

检查优先队列是否为空

我们使用 empty() 方法来检查 priority_queue 是否为空。此方法返回

• 1 (true) - 如果优先队列为空
• 0 (false) - 如果优先队列不为空

示例：C++ empty() 方法

#include <iostream>
#include <queue>
using namespace std;

int main() {

  // create a priority queue of ints
  priority_queue<string> languages;

  cout << "Is the queue empty? ";

  // check if the queue is empty  
  if (languages.empty()) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  cout << "Pushing elements..." << endl;

  // push element into the queue
  languages.push("Python");
  languages.push("C++");
  languages.push("Java");

  cout << "Is the queue empty? ";

  // check if the queue is empty
  if (languages.empty()) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }

  return 0;
}

输出

Is the queue empty? No
Popping all the elements
Is the queue empty? Yes

在上面的示例中，我们使用 empty() 方法来确定 languages 优先队列是否为空，

if (languages.empty()) {
  cout << "Yes" << endl;
}
else {
  cout << "No" << endl; 
}

最初，队列中没有元素。所以 languages.empty() 返回 true。

然后我们向队列中插入元素并再次使用 empty() 方法。这次，它返回 false。

最小堆优先队列

我们也可以创建一个最小堆 priority_queue，它按升序排列元素。其语法是

priority_queue<type, vector<type>, greater<type>> pq; 

例如，

// integers are arranged in ascending order
priority_queue<int, vector<int>, greater<int>> pq_integers;

在这种类型的优先队列中，最小的元素具有最高的优先级。

示例：最小堆优先队列

#include<iostream>
#include <queue>
using namespace std;

int main() {

  // create a priority queue of int
  // arranges elements in ascending order
  priority_queue<int, vector<int>, greater<int>> numbers;

  // add items to priority_queue
  numbers.push(1);
  numbers.push(20);
  numbers.push(7);

  // print element with highest priority
  cout << "Top element: " << numbers.top();

  return 0;
}

输出

Top element: 1