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)