c++ Priority queue usage point summary

  • 2020-06-23 01:39:00
  • OfStack

Detail c++ priority queue usage

Priority queues are also a form of data structure called queues. Its operations are not limited to fifO of the queue, but can be logical (maximum or minimum, etc.).

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 team 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. 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. Use pair as the priority queue element:

Rule: pair 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 . . .

That's the full details of c++ priority queue usage. If you have any additional information, please contact this site.


Related articles: