C++优先队列priority_queue_template argument for template type parameter must

优先队列（priority_queue）是C++标准模版库（STL）标准容器中容器适配器（container adapotor）的一种，复制数据结构中堆（heap）的结构和功能。优先队列没有独立的头文件，而是包含在头文件queue中，通过#include <queue>调用。

1. 类模版原型

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

优先队列的类模版原型共有三个模版类型参数，第一个是数据单元类型名，第二个是所使用的底层容器类类型名，第三个是比较类类型名，后两个模版类型参数都有默认参数。

2. 底层容器

优先队列作为容器适配器的一种，不是完整的容器类，需要借助于容器类比如vector和deque来实现堆的相应操作集。如类模版原型所示，其容器类参数默认使用vector。

3. 算法函数

除了底层容器，优先队列还通过自动调用STL算法库algorithm中的make_heap、push_heap和pop_heap函数来维持堆的特性。以下两段代码示例对比使用优先队列priority_queue与显性地使用vector和algorithm中的3个heap函数。

1. 优先队列priority_queue

#include <iostream>
#include <queue>

using namespace std;

int main(int argc, char const *argv[]) {
   
    int myints[] = {
   10,20,30,5,15};     // fixed-size array
    priority_queue<int> mypq(myints, myints+5);		// default max heap
    cout << "initial max heap   : " << mypq.top() << "\n";  // heap top
    
    mypq.pop();
    cout << "max heap after pop : " << mypq.top() << "\n";

    mypq.push(99);
    cout << "max heap after push: " << mypq.top() << "\n";

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

输出

initial max heap   : 30
max heap after pop : 20
max heap after push: 99
1
2
3

2. 使用组合vector、make_heap、push_heap和pop_heap

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char const *argv[]) {
   
    
1
2
3
4
5
6
7
8