priority_queue用法（大顶堆，小顶堆）总结

Priority queues

are a type of container adaptors（容器适配器）, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.

This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).

Priority queues are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are popped from the “back” of the specific container, which is known as the top of the priority queue.

The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall be accessible through random access iterators and support the following operations:（容器应通过随机访问迭代器访问，并支持以下操作）

empty()
size()
front()
push_back()
pop_back()

The standard container classes vector and deque fulfill these requirements. By default, if no container class is specified for a particular priority_queue class instantiation, the standard container vector is used.

Support of random access iterators is required to keep a heap structure internally at all times. This is done automatically by the container adaptor by automatically calling the algorithm functions make_heap, push_heap and pop_heap when needed.

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

示例

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <queue>
using namespace std;


/**
默认比较函数为less, 大顶堆
**/
void defaultCmpLess() {
    cout << "=========defaultCmpLess(big heap)========" << endl;
    priority_queue<int> q;
    for (int i = 0; i < 10; i++) {
        q.push(rand()%20);
    }

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

}

/**
使用greater比较函数，小顶堆
**/
void useCmpGreater() {
    cout << "=========useCmpGreater(small heap)========" << endl;
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 0; i < 10; i++) {
        q.push(rand()%20);
    }

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


//==========================

struct Node
{
    int x, y;
    Node(int a = 0, int b = 0):x(a), y(b){};
    friend bool operator<(const Node &a, const Node &b);

};
inline bool operator<(const Node &a, const Node &b) {
    if (a.x != b.x)
        return a.x < b.x;
    return a.y > b.y;
}

/**
运算符重载
**/
void overloadOperator() {
    cout << "=========overload Operator< =========" << endl;
    cout << "a.x < b.x; a.y > b.y" << endl;
    priority_queue<Node> q;
    for (int i = 0; i < 10; i++) {

        q.push( Node( rand()%20, rand()%20 ) );
    }

    while (!q.empty()) {
        cout << q.top().x << "," << q.top().y << endl;
        q.pop();
    } 
    cout << endl;   
}


//=========================
/**
自构建比较函数
**/
struct cmp2
{
    bool operator()(int a, int b) {
        return a < b;
    }
};

void designCmp() {
    cout << "=========designCmp========" << endl;
    cout << "operator a<b" << endl;
    priority_queue<int, vector<int>, cmp2 > q;

    for (int i = 0; i < 10; i++) {
        q.push(rand()%20);
    }

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

int main(int argc, char const *argv[])
{   
    defaultCmpLess();
    useCmpGreater();
    overloadOperator();
    designCmp();
}

运行结果