Jak mogę utworzyć Min stl priority_queue?


Domyślnie kolejka priorytetowa stl jest maksymalna (funkcja Top zwraca największy element).
Powiedzmy dla uproszczenia, że ​​jest to kolejka priorytetowa wartości int.
Zaproszony:
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

Użyj
std :: Greater
jako funkcji porównawczej:
std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

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
.
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

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
.
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

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]
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

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;
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

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();
}
}
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

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
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

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;
}

Aby odpowiedzieć na pytania, Zaloguj się lub Zarejestruj się