1、写在前面

大家好，今天记录的内容是：

priority_queue容器

2、内容

2.1、介绍

优先级队列（priority_queue）是一种容器适配器，该容器适配器模拟的是队列存储结构，其特点是：

新元素只能从一端（队尾）入队，从另一端（队头）出队；
每次只能访问priority_queue的队头元素；
队列的首元素是队列中所有元素的最大值或最小值。默认情况下，优先级队列会创建最大堆。
在priority_queue中，每个元素都会有一个优先级概念，会按照固定的顺序定义。

在C++ STL中，默认情况下，优先级队列（priority_queue）的首元素始终是最大的元素。当然，我们也可以将其修改为最小元素。需要注意，此时优先级队列并不遵循着“先入先出”（FIFO）的规则进行存取元素，而是每次只能访问队头元素，因此每次都是优先级最大的元素先出队。

2.2、优先级

在priority_queue容器适配器中，存储的元素会按照优先级的高低来排序，而队首元素则是优先级最大的元素。

那么，到底priority_queue的优先级是如何判定的呢？

其实，priority_queue容器适配器在创建的时候，就会定义元素存储的排序规则，按照这个规则就能让priority_queue容器适配器有一个确定的元素优先级规则。

举个例子，现在有一个priority_queue容器适配器，其指定的规则是按照元素值从小到大的顺序进行排序，那么按照这个排序规则，该priority_queue容器适配器的最小元素就是优先级最大的元素，因此也放置在队头位置。也就是说，每当有新元素入队，该priority_queue容器适配器就会按照从小到大的排序规则，找到优先级最大的元素并将其移动到队头位置，同样的，当priority_queue容器适配器从队头出队元素之后，它就会再找到当前优先级队列中优先级最高的元素并移动到队头位置。

2.3、参数

在C++ STL中，定义priority_queue最多可以传入三个参数，如下所示：

priority_queue<T, Container, Compare>

其中：

T：存储数据元素的具体类型，如int、double等
Container：指定优先级队列底层使用的基础容器（默认会使用vector容器），我们也可以指定使用deque容器。
Compare：指定优先级队列中元素存储的排序规则，由该规则就可以确定每个元素的优先级高低。默认使用less<T>，即从大到小的排序规则，此时构建的是最大堆。当然，我们也可以使用greater<T>，即按照从小到大的排序规则来存储元素，此时构建的是最小堆。

备注：std::less<T>和std::greater<T>都是以函数对象的方式定义在<function>头文件中。

2.4、创建优先级队列

首先，在创建priority_queue容器适配器前，程序必须包含以下代码：

#include <queue>
using namespace std;

这是因为priority_queue容器适配器是定义在<queue>头文件中，并且在std命名空间内有定义，因此需写入这两行代码才能使用priority_queue容器适配器。

(1) 创建空的 priority_queue

示例：

priority_queue<int> result;

上述代码创建了一个空的priority_queue容器适配器。

注意，上述优先级队列result没有指定底层容器，因此底层默认采用的是vector容器，排序方法是采用了默认的less<T>方法，生成的是最大堆。

(2) 使用数组指定范围内的数据初始化 priority_queue

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // 定义一个普通数组 arr 
    int arr[] {300, 100, 500, 200, 400};
    
    // 利用普通数组来初始化优先级队列 
    priority_queue<int> priorQue(arr, arr+5);
    
    // 输出优先级队列 
    cout << "优先级队列的元素为："; 
    while (!priorQue.empty()) {
        cout << priorQue.top() << " ";
        priorQue.pop();
    }
    cout << '\n';
    return 0;
}

运行结果为：

优先级队列的元素为：500 400 300 200 100

需要注意，如果想使用普通数组来初始化一个priority_queue容器适配器，则必须保证数组中存储的元素类型和priority_queue中指定的元素存储类型相同。

(3) 使用其他容器中指定范围内的数据初始化 priority_queue

示例：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    // 定义一个 vector 容器变量 v
    vector<int> v{400, 100, 500, 200, 300};

    // 利用 vector 容器来初始化优先级队列 
    priority_queue<int> priorQue(v.begin(), v.end());
    
    // 输出优先级队列 
    cout << "优先级队列的元素为："; 
    while (!priorQue.empty()) {
        cout << priorQue.top() << " ";
        priorQue.pop();
    }
    cout << '\n';
    return 0;
}

运行结果为：

优先级队列的元素为：500 400 300 200 100

同样的，如果想使用vector容器来初始化一个priority_queue容器适配器，则必须保证该vector容器中存储的元素类型和priority_queue中指定的元素存储类型相同。

(4) 创建时指定底层容器以及排序规则

前文提到，在优先级队列中，底层处理容器默认采用的是vector容器，我们可以指定使用deque容器。另外，排序规则默认使用的是less<T>，此时生成的优先级队列，元素值越大优先级越高，越靠近队头。我们可以指定为greater<T>，此时生成的是最小堆，即队列中元素按从小到大的顺序进行排序，元素值越小优先级越大。

示例：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    // 定义一个 vector 容器变量 v
    vector<int> v{400, 100, 500, 200, 300};
    
    // 利用 vector 容器来初始化优先级队列（生成最小堆） 
    priority_queue<int, deque<int>, greater<int> > priorQue(v.begin(), v.end());
    
    // 输出优先级队列 
    cout << "优先级队列的元素为："; 
    while (!priorQue.empty()) {
        cout << priorQue.top() << " ";
        priorQue.pop();
    }
    cout << '\n';
    return 0;
}

优先级队列的元素为：100 200 300 400 500

事实上，less<T>或greater<T>的应用不多，如果优先级队列中存储的元素数据类型不是基本数据类型，而是自定义类型，此时就需要我们自定义排序规则，自己定义元素比较方式。

2.5、成员函数

priority_queue容器适配器提供了若干成员函数，记录如下：

empty()

empty()函数用于检查优先级队列容器是否为空。如果队列为空，则返回1（表示true），否则返回0（表示false）。

举个例子：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // 定义优先级队列
    priority_queue<int> priorQue;
    
    // 判断语句 
    if(priorQue.empty()) {
        cout << "队列为空" << endl; 
    }
    else {
        cout << "队列不为空" << endl; 
    } 
    return 0;
}

运行结果：

队列为空

size()

size()函数用于返回priority_queue的大小，或者说是存储的元素个数。

举个例子：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    // 定义一个 vector 容器变量 v
    vector<int> v{400, 100, 500, 200, 300};
    
    // 利用 vector 容器来初始化优先级队列（生成最小堆） 
    priority_queue<int, deque<int>, greater<int> > priorQue(v.begin(), v.end());
    
    // 输出语句，调用size( )函数 
    cout<< "优先级队列中的元素个数为：" <<  priorQue.size();
    
    return 0;
}

运行结果：

优先级队列中的元素个数为：5

top()

top()函数用于返回priority_queue中第一个元素的引用形式，默认情况下该元素是队列中的最大值。

举个例子：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // 定义一个优先级队列 
    priority_queue<int> priorQue;
     
    // 入队四个元素 
    priorQue.push(2);
    priorQue.push(6);
    priorQue.push(8);
    priorQue.push(4);
 
    // 输出语句，调用 top() 函数 
    cout << "队头元素为：" <<priorQue.top();
    return 0;
}

运行结果：

队头元素为：8

push() 和 pop()

push()函数用于在优先级队列中插入新元素，即该元素将添加到优先级队列中，此时队列的大小会加1，并且优先级队列会按照事先规定好的排序规则对包含的元素进行重新排序，将新元素的副本存储到合适的位置上。
pop()函数用于删除优先级队列priority_queue中的第一个元素，也就是删除掉优先级最高的元素（顶部元素）。

举个例子，假定有五个整数，现在需要存入优先级队列中，并且求出所有整数的总和。

程序如下：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // sum 用于存储整数总和
    int sum = 0;

    // 定义优先级队列
    priority_queue<int> priorQue;

    // 存入五个数据
    priorQue.push(5);
    priorQue.push(1);
    priorQue.push(3);
    priorQue.push(9);
    priorQue.push(7);

    // 当前priorQue中元素排序为: 9, 7, 5, 3, 1

    // 如果当前队列不为空，则进行求和操作
    while ( !priorQue.empty() ) {
        // 将队头元素添加到 sum 中
        sum = sum + priorQue.top();
        // 弹出队头元素
        priorQue.pop();
    }
    // 最后输出结果
    cout << "sum:" << sum;
    return 0;
}

运行结果为：

sum:25

swap()

该函数用于将一个优先级队列中的内容与另一个相同类型和大小的优先级队列进行交换。也就是说，将两个priority_queue容器适配器中的元素进行互换，可以注意到，进行互换的2个priority_queue容器适配器中存储的元素类型以及底层采用的基础容器类型都必须相同。

举个例子：

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

// 自定义函数，用于输出优先级队列中的元素 
void show(priority_queue<int> pqueue) {
    priority_queue<int> q = pqueue;
    while (!q.empty()) {
        cout << q.top( ) << "  "; 
        q.pop();
    }
    cout << '\n';
}
// 主函数 
int main() {
    // 定义两个优先级队列 
    priority_queue<int> priorQue1;
    priority_queue<int> priorQue2; 
 
    // 存入数据元素到 priorQue1
    priorQue1.push(2);
    priorQue1.push(8);
    priorQue1.push(4);
    priorQue1.push(6);

 
    // 存入数据元素到 priorQue2
    priorQue2.push(1);
    priorQue2.push(7);
    priorQue2.push(3);
    priorQue2.push(5);

    cout <<"交换前：" << endl;
    cout << "队列1：";
    show(priorQue1);
    cout << "队列2：";
    show(priorQue2);
    
    // 交换两个优先级队列的内容 
    priorQue1.swap(priorQue2);
    cout << "------------------" << endl;
    
    cout <<"交换后：" << endl;
    cout << "队列1：";
    show(priorQue1);
    cout << "队列2：";
    show(priorQue2);
    
    return 0;
}

交换前：
队列1：8  6  4  2
队列2：7  5  3  1
------------------
交换后：
队列1：7  5  3  1
队列2：8  6  4  2

emplace()

emplace()函数用于将新元素插入优先级队列中，在队列中的合适位置直接生成新元素，它很类似push()函数，不同点在于emplace()函数保存了对象的不必要副本。

举个例子：

#include <iostream>
#include <queue>
using namespace std;
 
int main() {
    // 定义一个优先级队列 
    priority_queue<int> priorQue;
    
    // 入队6个新元素 
    priorQue.emplace(5);
    priorQue.emplace(3);
    priorQue.emplace(2);
    priorQue.emplace(4);
    priorQue.emplace(6);
    priorQue.emplace(1);
 
    // 输出语句 
    cout << "priorQue : ";
    while (!priorQue.empty()) {
        cout << priorQue.top() << " ";
        priorQue.pop();
    }
 
    return 0;
}

priorQue : 6 5 4 3 2 1

3、写在最后

好了，文章的内容就到这里，感谢观看。

【C++学习笔记】：priority_queue 容器

1、写在前面

2、内容

2.1、介绍

2.2、优先级

2.3、参数

2.4、创建优先级队列

(1) 创建空的 priority_queue

(2) 使用数组指定范围内的数据初始化 priority_queue

(3) 使用其他容器中指定范围内的数据初始化 priority_queue

(4) 创建时指定底层容器以及排序规则

2.5、成员函数

empty()

size()

top()

push() 和 pop()

swap()

emplace()

3、写在最后

容器服务

热门文章

最新文章

相关课程

相关电子书

相关实验场景