La cola de prioridad stl predeterminada es Max one (la función Top devuelve el elemento más grande).
Digamos, por simplicidad, que es una cola de prioridad de valores int.
fuente
La cola de prioridad stl predeterminada es Max one (la función Top devuelve el elemento más grande).
Digamos, por simplicidad, que es una cola de prioridad de valores int.
Utilizar std::greater
como función de comparación:
std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;
Una forma sería definir un comparador adecuado con el que operar en la cola de prioridad ordinaria, de modo que su prioridad se invierta:
#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();
}
Lo que generaría 1, 3, 5, 8 respectivamente.
Aquí se dan algunos ejemplos del uso de colas de prioridad a través de STL y las implementaciones de Sedgewick .
El tercer parámetro de plantilla para priority_queue
es el comparador. Configúrelo para usarlo greater
.
p.ej
std::priority_queue<int, std::vector<int>, std::greater<int> > max_queue;
Que necesita #include <functional>
para std::greater
.
Puede hacerlo de varias formas:
1. Utilizando greater
como función de comparación:
#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. Insertar valores cambiando su signo (usando menos (-) para un número positivo y usando más (+) para un número negativo:
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. Usando una estructura o clase personalizada:
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. Usando una estructura o clase personalizada, puede usar priority_queue en cualquier orden. Supongamos que queremos clasificar a las personas en orden descendente según su salario y, si están empatadas, según su edad.
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;
}
El mismo resultado se puede obtener sobrecargando al operador:
struct people
{
int age,salary;
bool operator< (const people & p)const
{
if(salary==p.salary)
{
return age>p.age;
}
else
{
return salary>p.salary;
}
}};
En función principal:
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;
}
bool operator > (const people & p)const
a 5) sobrecarga de operadores
<
sobrecarga así, es mejor sobrecargar >
y usargreater<people>
En C ++ 11 también puede crear un alias por conveniencia:
template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
Y utilícelo así:
min_heap<int> my_heap;
Una forma de resolver este problema es presionar el negativo de cada elemento en priority_queue para que el elemento más grande se convierta en el elemento más pequeño. A la hora de realizar la operación pop, se toma la negación de cada elemento.
#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();
}
}
Basándome en todas las respuestas, creé un código de ejemplo sobre cómo crear una cola de prioridad. Nota: Funciona con compiladores C ++ 11 y superiores
#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;
}
Salida del código anterior
Enter number of elements N = 4
33 | 535
49 | 411
411 | 49
535 | 33
Podemos hacer esto de varias formas.
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;
}
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;
}
operator>
, con lo que funcionaría a la perfecciónstd::greater
. También puede escribir su propio functor en lugar destd::greater
si lo desea.operator<
;)vector
ydeque
cumplen los requisitos que debe cumplir un contenedor subyacente para una priority_queue. También puede utilizar una clase de contenedor personalizada. Puede encontrar una explicación muy elaborada en cplusplus.com/reference/queue/priority_queue