c++ priority queue of priority_queue

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

In a priority queue, elements are given priority. When accessing an element, the element with the highest priority is removed first. Priority queues have the behavior characteristics of the highest first out (first in, largest out).

First, include the header file #include < queue > The difference between queue and queue is that we can customize the priority of the data in the queue, so that the one with high priority goes to the front of the queue and gets out first.

A priority queue has all the characteristics of a queue, including the basic operation of the queue, but adds an internal sort on top of it, which is essentially implemented by a heap.

Same as the queue basic operation:

top accesses the team header element Whether the empty queue is empty size returns the number of elements in the queue push inserts elements to the end of the queue (and sorts) emplace constructs 1 element in situ and inserts it into the queue pop pop-up header element 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 arrays, such as vector,deque, etc., but not list. STL default is vector), Functional is the way to compare.

You only need to pass in these three parameters when you need to use a custom data type, and you only need to pass in the data type when using the basic data type, which defaults to the large top heap.
1 a:

// Ascending order queue 
priority_queue <int,vector<int>,greater<int> > q;
// Descending order queue 
priority_queue <int,vector<int>,less<int> >q;

//greater and less is std The implementation of the two affine functions (is to make 1 The use of the class looks like 1 A function. The implementation is the implementation in the class 1 a operator() , the class has functionally similar behavior, is 1 A class of affine functions.) 

1. Examples of priority queues of basic types:

#include<iostream>
#include <queue>
using namespace std;
int main() 
{
  // For the base type   The default is large top heap 
  priority_queue<int> a; 
  // Is equivalent to  priority_queue<int, vector<int>, less<int> > a;
  
  //    Here, 1 Make sure there is a space, otherwise it will be a right shift operator ↓ 
  priority_queue<int, vector<int>, greater<int> > c; // So this is a little top heap 
  priority_queue<string> b;

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

  while (!c.empty()) 
  {
    cout << c.top() << ' ';
    c.pop();
  }
  cout << endl;

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

Operation results:

[

4 3 2 1 0
0 1 2 3 4
cbd abcd abc
Please press any key to continue..

]

2. pair is used as the priority queue element:

Rule: pair's comparison, first compare the first element, the first equal compare the second.

#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 << ' ' << a.top().second << '\n';
    a.pop();
  }
}

Operation results:

[

2 5
1 3
1 2
Please press any key to continue..

]

3. An example of using custom types as priority queue elements

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

// methods 1
struct tmp1 // Operator overloading <
{
  int x;
  tmp1(int a) {x = a;}
  bool operator<(const tmp1& a) const
  {
    return x < a.x; // Big pile top 
  }
};

// methods 2
struct tmp2 // Rewrite the function 
{
  bool operator() (tmp1 a, tmp1 b) 
  {
    return a.x < b.x; // Big pile top 
  }
};

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 << '\n';
    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 << '\n';
    f.pop();
  }
}

Operation results:

[

3
2
1

3
2
1
Please press any key to continue..

]