STL模板类priority_queue详解

概述

priority_queue是C++ STL标准库中的一种数据结构，实现了一个可以加入和删除元素的堆（heap）数据结构。通常情况下，priority_queue会以向量vector容器作为底层容器（默认情况下）。

priority_queue适合用于需要对数据进行排序的场景，如：Dijkstra算法、Prim算法、贪心算法等等。如果数据的优先级可以用一个数字来表示且这个数字大的优先级高，则可以使用priority_queue。

需要注意的是，堆有很多种，并不一定是最大值在堆顶的大根堆，也可以是最小值在堆顶的小根堆。

构造函数

priority_queue类的构造函数有以下几种：

默认构造函数

priority_queue<Type, Container, Comparator> pq;

使用底层容器Container，元素类型为Type，比较器为Comparator来构造一个空的priority_queue。

默认情况下，底层容器为vector<Type>，比较器为less<Type>。

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

int main(){
    priority_queue<int> pq1; //默认底层容器为vector，比较器为less<int>
    priority_queue<int, vector<int>, less<int> > pq2; //明确底层容器和比较器
    return 0;
}

单参数构造函数

priority_queue<Type, Container, Comparator> pq(Container& ctnr);

使用容器ctnr构造一个新的priority_queue对象。

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

int main(){
    vector<int> v = {3, 1, 4, 1, 5, 9};
    priority_queue<int> pq(v); 

    return 0;
}

双参数构造函数

priority_queue<Type, Container, Comparator> pq(Container& ctnr, const Comparator& cmp);

使用容器ctnr和比较器cmp构建一个新的priority_queue对象。

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

int main(){
    vector<int> v = {3, 1, 4, 1, 5, 9};
    priority_queue<int, vector<int>, greater<int> > pq(v);

    return 0;
}

成员函数

push()

void pq.push(const Type& val);

将值val插入到优先队列的底部，并根据队列的定义重新排列底层容器中的元素以保持堆的性质。

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

int main(){
    priority_queue<int> pq;
    pq.push(1);
    pq.push(5);
    pq.push(4);
    pq.push(2);
    pq.push(3);//通过push()插入元素

    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;

}

输出结果：

5 4 3 2 1 

pop()

void pq.pop();

将队首元素弹出优先队列。

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

int main(){
    priority_queue<int> pq;

    for(int i = 1; i <= 5; ++i)
    {
        pq.push(i);   
    }

    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop(); //通过pop()弹出元素
    }
    return 0;
}

输出结果：

5 4 3 2 1

top()

Type& pq.top();

返回队首元素的引用。

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

int main(){
    priority_queue<int> pq;
    pq.push(3);
    pq.push(2);
    pq.push(1);

    while(!pq.empty()){
        cout<<pq.top()<<" "; //通过top()访问队首元素
        pq.pop();
    }
    return 0;
}

输出结果：

3 2 1

empty()

bool pq.empty() const;

判断容器是否为空。

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

int main(){
    priority_queue<int> pq;
    
    cout << pq.empty(); // 1

    return 0;
}

输出结果：

1

size()

size_t pq.size() const;

返回容器内元素的个数。

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

int main(){
    priority_queue<int> pq;
    pq.push(5);
    pq.push(4);
    pq.push(3);
    pq.push(2);
    pq.push(1);

    cout << pq.size(); // 5

    return 0;
}

输出结果：

5

emplace()

template <class... Args>
void pq.emplace(Args&&... args)

C++11新增的一个方法。用于原位构造的形式插入元素，并在底层容器中维护堆的性质。

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

struct Object{
    int a;
    string b;
    Object(int _a, string _b):a(_a),b(_b){}
    bool operator < (const Object& o) const { //定义比较运算符
        return a < o.a;
    }
};

int main(){
    priority_queue<Object> pq;
    pq.emplace(5, "Hello"); //通过emplace()插入元素
    pq.emplace(4, "World");
    pq.emplace(3, "C++11");
    pq.emplace(2, "new feature");

    while(!pq.empty()){
        cout<<pq.top().b<<" "; 
        pq.pop(); 
    } 
    return 0; 
}

输出结果：

5 4 3 2 

swap()

void pq.swap(priority_queue& x);

C++11新增的一个方法，用于将priority_queue对象x和当前对象进行交换。

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

int main(){
    priority_queue<int> pq1;
    pq1.push(5);
    pq1.push(4);
    pq1.push(3);

    priority_queue<int> pq2;
    pq2.push(9);
    pq2.push(8);
    pq2.push(7);

    pq1.swap(pq2); // 通过swap()交换pq1和pq2

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

    cout<<endl;

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

    return 0;
}

输出结果：

9 8 7 
5 4 3 

operator=

priority_queue& pq.operator=(priority_queue&& pq) noexcept;
priority_queue& pq.operator=(const priority_queue& pq) = default;

用于将一个priority_queue对象赋值给另一个对象。

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

int main(){
    priority_queue<int> pq1;
    pq1.push(5);
    pq1.push(4);
    pq1.push(3);

    priority_queue<int> pq2;
    pq2.push(9);
    pq2.push(8);
    pq2.push(7);

    pq2 = pq1; //通过operator=将pq2赋值为pq1

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

    return 0;
}

输出结果：

5 4 3 

总结

priority_queue作为C++ STL标准库中的一个数据结构，可以实现堆的形式，可以用于各种需要排序的场景。在使用时，需要注意元素类型、底层容器类型、比较器类型、以及对push()、emplace()、pop()等成员函数的正确调用。在C++11及以上版本中，还新增了emplace()和swap()方法，使用更方便。