当前位置：极客教程 > C++语言 > C++ 教程 > C++标准模板库中的优先队列

C++标准模板库中的优先队列

C++标准模板库中的优先队列

C++优先队列 是一种容器适配器，特别设计成队列的第一个元素是队列中所有元素中最大的还是最小的元素，并且元素是非递减或非递增的顺序（因此我们可以看到队列的每个元素都有一个优先级{固定顺序}）。

在C++的STL中，默认情况下，队列的顶端元素总是最大的。我们还可以将其更改为顶端的最小元素。优先队列是建立在最大堆的基础之上，并使用数组或向量作为内部结构。简单来说， STL优先队列 是堆数据结构的实现。

语法：

std::priority_queue<int> pq;

例子：

// C++ program to demonstrate
// the use of priority_queue
#include <iostream>
#include <queue>
using namespace std;

// driver code
int main() 
{
    int arr[6] = {10, 2, 4, 8, 6, 9};

    // defining priority queue
    priority_queue<int> pq;

    // printing array
    cout << "Array:";
    for(auto i: arr){
        cout << i << ' ';
    }
    cout << endl;

    // pushing array elements into the queue
    for(int i = 0; i < 6; i++){
        pq.push(arr[i]);
    }

    // pop elements from the priority queue
    cout << "Priority Queue: ";
    while(!pq.empty()){
        cout << pq.top() << ' ';
        pq.pop();
    }

    return 0;
}

输出：

Array: 10 2 4 8 6 9 
Priority Queue: 10 9 8 6 4 2

C++标准模板库中的优先队列

最大堆优先队列（默认方案）

如何为优先队列创建最小堆？

正如我们之前看到的，C++中的优先队列默认实现为最大堆，但是，它还提供了另一个参数来将其更改为最小堆，方法是在创建优先队列时传递另一个参数。

语法：

priority_queue <int, vector<int>, greater<int>> gq;

例子：

// C++ program to demonstrate
// min heap for priority queue
#include <iostream>
#include <queue>
using namespace std;

void showpq(priority_queue<int, vector<int>, greater<int>> gq)
{
    priority_queue<int, vector<int>, greater<int>> g = gq;
    while (!g.empty()){
        cout << ' ' << g.top();
        g.pop();
    }
    cout << '\n';
}

void showArray(int* arr, int n)
{
    for (int i = 0; i < n; i++){
        cout << arr[i] << ' ';
    }
    cout << endl;
}

// Driver Code
intmain()
{
    int arr[6] = {10, 2, 4, 8, 6, 9};
    priority_queue<int, vector<int>, greater<int>> gquiz(arr, arr + 5);

    cout << "Array: ";
    showArray(arr, 6);

    cout << "Priority Queue: ";
    showpq(gquiz);

    return 0;
}

输出：

The priority queue gquiz is : 2 4 6 8 9 10

gquiz.size() : 6
gquiz.top() : 2
gquiz.pop() : 4 6 8 9 10

C++标准模板库中的优先队列

最小堆优先队列

注意： 上述语法可能难以记忆，因此在数字值的情况下，我们可以将值乘以-1并使用max heap获取min heap的效果。不仅如此，我们还可以通过替换 大于（greater） 与自定义比较函数来使用自定义排序方法。

优先队列的方法

下面是std::priority_queue类的所有方法的列表：

方法 定义
priority_queue::empty() 返回队列是否为空。
priority_queue::size() 返回队列的大小。
priority_queue::top() 返回队列中优先级最高的元素的引用。
priority_queue::push() 将元素‘g’添加到队列的末尾。
priority_queue::pop() 删除队列的第一个元素。
priority_queue::swap() 用于交换两个队列的内容，但这两个队列必须是相同类型的，尽管大小可能不同。
priority_queue::emplace() 用于向优先队列容器中插入新元素。
priority_queue value_type 表示作为优先队列中元素存储的对象类型。它是模板参数的代名词。

C++中的优先队列操作

1. 插入和删除优先队列元素

使用 push() 方法插入元素到优先队列中，使用 pop() 方法删除具有最高优先级的元素。

下面是C++程序的各种优先队列函数：

// C++ Program to demonstrate various
//  method/function in Priority Queue
#include <iostream>
#include <queue>
using namespace std;
 
// Implementation of priority queue
void showpq(priority_queue<int> gq)
{
    priority_queue<int> g = gq;
    while (!g.empty()) {
        cout << ' ' << g.top();
        g.pop();
    }
    cout << '\n';
}
 
// Driver Code
int main()
{
    priority_queue<int> gquiz;
    // used in inserting the element
    gquiz.push(10);
    gquiz.push(30);
    gquiz.push(20);
    gquiz.push(5);
    gquiz.push(1);
 
    cout << "The priority queue gquiz is : ";
     
    // used for highlighting the element
    showpq(gquiz);
 
    // used for identifying the size
    // of the priority queue
    cout << "\ngquiz.size() : " <<
             gquiz.size();
    // used for telling the top element
    // in priority queue
    cout << "\ngquiz.top() : " <<
             gquiz.top();
 
    // used for popping the element
    // from a priority queue
    cout << "\ngquiz.pop() : ";
    gquiz.pop();
    showpq(gquiz);
 
    return 0;
}

输出

// The priority queue gquiz is : 30 20 10 5 1

gquiz.size() : 5
gquiz.top() : 30
gquiz.pop() : 20 10 5 1

注 ：上述是一种优先队列初始化方法。

2. 访问优先队列的顶部元素

可以使用 _top() _ 方法访问优先队列的顶部元素。

// C++ program to demonstrate
// Implementation of swap() function
#include <iostream>
#include <queue>
using namespace std;
 
// Driver code
int main()
{
  // create a priority queue of int
  priority_queue<int> q1, q2;
  q1.push(10);
  q1.push(20);
  q1.push(30);
 
  // display priority queue
  cout << "First Element: " << q1.top();
  cout << ", Size: " << q1.size() << endl;
 
  q2.push(50);
  q2.push(100);
  q2.push(30);
 
  // display priority queue
  cout << "Second Element: " << q2.top();
  cout << ", Size: " << q2.size() << endl;
 
  // swaping of priority queue
  q1.swap(q2);
 
  // display priority queue
  cout << "First Element: " << q1.top();
  cout << ", Size: " << q1.size() << endl;
 
  cout << "Second Element: " << q2.top();
  cout << ", Size: " << q2.size() << endl;
 
  return 0;
}

输出

First Element: 30, Size: 3
Second Element: 100, Size: 3
First Element: 100, Size: 3
Second Element: 30, Size: 3

// CPP程序来说明
// swap()函数的实现
 
#include <bits/stdc++.h>
using namespace std;
 
// 输出优先队列的元素
void print(priority_queue<int> pq)
{
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
}
 
int main()
{
    // 声明优先队列容器
    priority_queue<int> pq1;
    priority_queue<int> pq2;
 
    // 将元素推入第一个优先队列
    pq1.push(1);
    pq1.push(2);
    pq1.push(3);
    pq1.push(4);
 
    // 将元素推入第二个优先队列
    pq2.push(3);
    pq2.push(5);
    pq2.push(7);
    pq2.push(9);
 
    cout << "交换前：" << endl;
    cout << "优先队列 1 = ";
    print(pq1);
    cout << "优先队列 2 = ";
    print(pq2);
 
    // 使用swap()函数交换优先队列中的元素
    pq1.swap(pq2);
 
    cout << endl << "交换后：" << endl;
    cout << "优先队列 1 = ";
    print(pq1);
    cout << "优先队列 2 = ";
    print(pq2);
    return 0;
}

输出

交换前：
优先队列 1 = 4 3 2 1 
优先队列 2 = 9 7 5 3 

交换后：
优先队列 1 = 9 7 5 3 
优先队列 2 = 4 3 2 1

5. 将新元素插入优先队列容器

emplace() 函数用于将新元素插入优先队列容器中，新元素根据其优先级添加到优先队列中。它类似于push操作。不同之处在于，emplace（）操作避免了对象的不必要复制。

下面是在C++中将新元素插入优先队列容器的示例程序：

// CPP程序来说明
// emplace()函数的实现
 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    priority_queue<int> pq;
    pq.emplace(1);
    pq.emplace(2);
    pq.emplace(3);
    pq.emplace(4);
    pq.emplace(5);
    pq.emplace(6);
    //优先队列变成1, 2, 3, 4, 5, 6
 
    // 打印输出优先队列
    cout << "优先队列 = ";
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
 
    return 0;
}

输出

优先队列 = 6 5 4 3 2 1

6. 表示存储在优先队列元素中的对象类型

priority_queue :: value_type方法是C++ STL中的一个内置函数，用于表示存储为优先队列元素的对象类型。它作为模板参数的同义词。

语法：

priority_queue::value_type variable_name

下面是在C++中表示存储在优先队列元素中的对象类型的示例程序：

// C++程序，演示优先队列::value_type函数
 
#include <bits/stdc++.h>
using namespace std;
 
// 主程序
int main()
{
    // 为优先队列声明整数value_type
    priority_queue<int>::value_type AnInt;
 
    // 为优先队列声明字符串value_type
    priority_queue<string>::value_type AString;
 
    // 声明优先队列
    priority_queue<int> q1;
    priority_queue<string> q2;
 
    // AnInt 在这里作为int数据类型的变量
    AnInt = 20;
    cout << "value_type是AnInt = " << AnInt << endl;
    q1.push(AnInt);
    AnInt = 30;
    q1.push(AnInt);
    cout << "整数优先队列的头元素是: "
         << q1.top() << endl;
 
    // AString 在这里作为string数据类型的变量
    AString = "geek";
    cout << endl
         << "value_type是AString = " << AString
         << endl;
    q2.push(AString);
    AString = "for";
    q2.push(AString);
    AString = "geeks";
    q2.push(AString);
 
    cout << "字符串优先队列的头元素是: "
         << q2.top() << endl;
 
    return 0;
}

输出

value_type是AnInt = 20
整数优先队列的头元素是: 30

value_type是AString = geek
字符串优先队列的头元素是: geeks

所有操作的复杂度:

方法 时间复杂度 辅助空间
priority_queue::empty() O(1) O(1)
priority_queue::size() O(1) O(1)
priority_queue::top() O(1) O(1)
priority_queue::push() O(logN) O(1)
priority_queue::pop() O(logN) O(1)
priority_queue::swap() O(1) O(N)
priority_queue::emplace() O(logN) O(1)
priority_queue value_type O(1) O(1)

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

C++ 教程