Detailed explanation of c++ priority queue usage

c Detailed explanation of priority queue usage

Priority queue is also a kind of data structure such as queue. Its operation is not limited to first-in-first-out of the queue, but can also be done logically (exiting the queue according to the maximum value or minimum value, etc.).

Recommended learning: c Video tutorial

A normal queue is a first-in, first-out data structure. Elements are appended to the end of the queue and deleted from the head of the queue.

In a priority queue, elements are given priority. When elements are accessed, the element with the highest priority is removed first. The priority queue has the behavioral characteristics of first in, largest out.

First of all, we must include the header file #include. The difference between it and queue is that we can customize the priority of the data in it, so that the ones with higher priority will be placed at the front of the queue. Get priority out of the queue.

The priority queue has all the characteristics of the queue, including the basic operations of the queue. It just adds an internal sorting on this basis. It is essentially implemented as a heap.

The basic operation is the same as that of the queue:

top accesses the head element of the queue

empty whether the queue is empty

size returns the number of elements in the queue

push Insert elements to the end of the queue (and sort)

emplace Construct an element in place and insert it into the queue

pop Pop the element at the head of the queue

swap Exchange Content

Definition: priority_queue<Type, Container, Functional>

Type is the data type, Container is the container type (Container must be a container implemented with an array , such as vector, deque, etc., but list cannot be used. Vector is used by default in STL), and Functional is the comparison method.

When you need to use a custom data type, you need to pass in these three parameters. When using a basic data type, you only need to pass in the data type. The default is a big heap.

Generally:

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

1. Example of basic type priority queue:

#include<iostream>
#include <queue>
using namespace std;
int main() 
{
    //对于基础类型 默认是大顶堆
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;
    
    //      这里一定要有空格，不然成了右移运算符↓↓
    priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆
    priority_queue<string> b;

    for (int i = 0; i < 5; i++) 
    {
        a.push(i);
        c.push(i);
    }
    while (!a.empty()) 
    {
        cout << a.top() << &#39; &#39;;
        a.pop();
    } 
    cout << endl;

    while (!c.empty()) 
    {
        cout << c.top() << &#39; &#39;;
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while (!b.empty()) 
    {
        cout << b.top() << &#39; &#39;;
        b.pop();
    } 
    cout << endl;
    return 0;
}

Running result:

4 3 2 1 0
0 1 2 3 4
cbd abcd abc
请按任意键继续. . .

2. Example of using pair as a priority queue element:

Rule: For pair comparison, compare the first element first, and compare the second element if the first one is equal.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() 
{
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << &#39; &#39; << a.top().second << &#39;\n&#39;;
        a.pop();
    }
}

Run result:

2 5
1 3
1 2
请按任意键继续. . .

3. Example of using custom type as priority queue element

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

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << &#39;\n&#39;;
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(b);
    f.push(c);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << &#39;\n&#39;;
        f.pop();
    }
}

Run result:

3
2
1
 
3
2
1
请按任意键继续. . .

The above is the detailed content of Detailed explanation of c++ priority queue usage. For more information, please follow other related articles on the PHP Chinese website!