Jak mogę utworzyć Min stl priority_queue?

Użyj

std :: Greater

jako funkcji porównawczej:

std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;

Jednym ze sposobów byłoby zdefiniowanie odpowiedniego komparatora do pracy z normalną kolejką priorytetową, tak aby jej priorytet był odwrócony:

#include <iostream> 

 #include <queue> 

 using namespace std;  struct compare 

 { 

 bool operator()(const int& l, const int& r) 

 { 

 return l > r; 

 } 

 };  int main() 

 { 

 priority_queue<int,vector<int>, compare > pq;  pq.push(3); 

 pq.push(5); 

 pq.push(1); 

 pq.push(8); 

 while ( !pq.empty() ) 

 { 

 cout << pq.top() << endl; 

 pq.pop(); 

 } 

 cin.get(); 

 }

Który wyświetli odpowiednio 1, 3, 5, 8.
Tutaj
http://www.technical-recipes.c ... in-c/
pokazuje kilka przykładów użycia kolejek priorytetowych przy użyciu

Implementacje STL i Sedgewick
http://www.cs.princeton.edu/~r ... e.txt
.

Trzecim parametrem szablonu dla

priority_queue

jest komparator. Ustaw go tak, aby używał

większego

.
dawny.

std::priority_queue<int, std::vector<int>, std::greater<int> > max_queue;

Będziesz potrzebować

#include & < funkcjonal & >

dla

std :: Greater

.

Możesz to zrobić na kilka sposobów:

1. Używanie

Greater

jako funkcji porównawczej:

#include <bits/stdc++.h>using namespace std;int main()

{

 priority_queue<int,vector<int>,greater<int> >pq;

 pq.push(1);

 pq.push(2);

 pq.push(3); while(!pq.empty())

 {

 int r = pq.top();

 pq.pop();

 cout<<r<< " ";

 }

 return 0;

}

2. wstawianie wartości poprzez zmianę ich znaku (używając minus (-) dla liczby dodatniej i plus (+) dla liczby ujemnej:

int main()

{

 priority_queue<int>pq2;

 pq2.push(-1);//for +1

 pq2.push(-2);//for +2

 pq2.push(-3);//for +3

 pq2.push(4);//for -4 while(!pq2.empty())

 {

 int r = pq2.top();

 pq2.pop();

 cout<<-r<<" ";

 } return 0;

}

3. Korzystanie z niestandardowej struktury lub klasy:

struct compare

{

 bool operator()(const int & a, const int & b)

 {

 return a>b;

 }

};int main()

{ priority_queue<int,vector<int>,compare> pq;

 pq.push(1);

 pq.push(2);

 pq.push(3); while(!pq.empty())

 {

 int r = pq.top();

 pq.pop();

 cout<<r<<" ";

 } return 0;

}

4. Korzystając z niestandardowej struktury lub klasy, możesz użyć Priority_queue w dowolnej kolejności.
Załóżmy, że chcemy posortować ludzi w porządku malejącym według ich wynagrodzenia, a jeśli połączymy, to według wieku.

struct people

 {

 int age,salary; };

 struct compare{

 bool operator()(const people & a, const people & b)

 {

 if(a.salary==b.salary)

 {

 return a.age>b.age;

 }

 else

 {

 return a.salary>b.salary;

 } }

 };

 int main()

 { priority_queue<people,vector<people>,compare> pq;

 people person1,person2,person3;

 person1.salary=100;

 person1.age = 50;

 person2.salary=80;

 person2.age = 40;

 person3.salary = 100;

 person3.age=40;

 pq.push(person1);

 pq.push(person2);

 pq.push(person3); while(!pq.empty())

 {

 people r = pq.top();

 pq.pop();

 cout<<r.salary<<" "<<r.age<<endl;

 }

<ol start="5">
[*]
Ten sam wynik można uzyskać przy przeciążeniu operatora:

struct people

{

int age,salary;bool operator< (const people & p)const

{

 if(salary==p.salary)

 {

 return age>p.age;

 }

 else

 {

 return salary>p.salary;

 }

}};

W głównej funkcji:

priority_queue<people> pq;

people person1,person2,person3;

person1.salary=100;

person1.age = 50;

person2.salary=80;

person2.age = 40;

person3.salary = 100;

person3.age=40;

pq.push(person1);

pq.push(person2);

pq.push(person3);while(!pq.empty())

{

 people r = pq.top();

 pq.pop();

 cout<<r.salary<<" "<<r.age<<endl;

}

[/*]
[/list]

W C ++ 11 możesz również dla wygody utworzyć alias:

template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;

I użyj tego w ten sposób:

min_heap<int> my_heap;

Jednym ze sposobów rozwiązania tego problemu jest umieszczenie ujemnego elementu każdego elementu w Priority_queue, tak aby największy element stał się najmniejszym. Weź negację każdego elementu podczas operacji pop.

#include<bits/stdc++.h>

using namespace std;int main(){

 priority_queue<int> pq;

 int i;// push the negative of each element in priority_queue, so the largest number will become the smallest number for (int i = 0; i < 5; i++)

 {

 cin>>j;

 pq.push(j*-1);

 } for (int i = 0; i < 5; i++)

 {

 cout<<(-1)*pq.top()<<endl;

 pq.pop();

 }

}

W oparciu o powyższe odpowiedzi utworzyłem przykładowy kod do utworzenia kolejki priorytetowej.

Uwaga: działa z kompilatorami C ++ 11 i nowszymi

#include <iostream>

#include <vector>

#include <iomanip>

#include <queue>using namespace std;// template for prirority Q

template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T> using max_heap = priority_queue<T, std::vector<T>>;const int RANGE = 1000;vector<int> get_sample_data(int size);int main(){

 int n;

 cout << "Enter number of elements N = " ; cin >> n;

 vector<int> dataset = get_sample_data(n); max_heap<int> max_pq;

 min_heap<int> min_pq;// Push data to Priority Queue

 for(int i: dataset){

 max_pq.push(i);

 min_pq.push(i);

 } while(!max_pq.empty() && !min_pq.empty()){

 cout << setw(10) << min_pq.top()<< " | " << max_pq.top() << endl;

 min_pq.pop();

 max_pq.pop();

 }}

vector<int> get_sample_data(int size){

 srand(time(NULL));

 vector<int> dataset;

 for(int i=0; i<size; i++){

 dataset.push_back(rand()%RANGE);

 }

 return dataset;

}

Wyświetl powyższy kod

Enter number of elements N = 4 33 | 535

 49 | 411

 411 | 49

 535 | 33

Możemy to zrobić na kilka sposobów.

Korzystanie z parametru komparatora wzorców
>

int main() 

 {

 priority_queue<int, vector<int>, greater<int> > pq; pq.push(40);

 pq.push(320);

 pq.push(42);

 pq.push(65);

 pq.push(12); cout<<pq.top()<<endl;

 return 0;

 }

Używanie określonej klasy porównawczej
>

struct comp

 {

 bool operator () (int lhs, int rhs)

 {

 return lhs > rhs;

 }

 }; int main()

 {

 priority_queue<int, vector<int>, comp> pq; pq.push(40);

 pq.push(320);

 pq.push(42);

 pq.push(65);

 pq.push(12); cout<<pq.top()<<endl; return 0;

 }