C++ STL priority queue

Coada de priorități este o structură de date de tip coadă, în care se fac operații de inserare și eliminare, dar ordinea nu este cea a cozii obișnuite. Fiecare element are asociată o anumită prioritate (de exemplu chiar valoarea sa), iar elementul de la începutul cozii este cel cu prioritate maximă, el fiind și cel care va fi eliminat din coadă în cazul operației de eliminare a unui element.

Cozile de priorități pot fi implementate sub formă de heap-uri, iar STL contine containerul adaptor priority_queue. Tehnic priority_queue implementează în mod implicit un max-heap.

Operația de determinare a elementului maxim are complexitate constantă, in timp ce operațiile de inserare și eliminare au complexități logaritmice în raport cu numărul de elemente.

Declarare

Clasa priority_queue este o clasă template definită în headerul queue:

#include <queue>

O putem declara ca în exemplul următor:

priority_queue<int> H;

Implicit, priority_queue-ul este un max-heap (elementul maxim are prioritate maximă) și se implementează pe baza operației < (less<int>)). Dacă dorim să gestionăm un min-heap (elementul minim să aibă prioritate maximă) vom folosi următoarea declarație:

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

Similar, putem crea cozi de priorităti cu elemente de tipuri oarecare T. Condiția este să fie definit pentru tipul T operatorul < (functorul less<T>), sau să construim un functor de comparare.

struct fcmp
{	bool operator()(const T & a , const T & b)
	{
		//returneaza true daca si numai daca a este strict in fata lui b in ordinea dorita
	}
};
priority_queue<T , vector<T> , fcmp > H;

Operații de bază

Fie următoarea coadă de priorități:

priority_queue<T> H;
T v;

Adăugarea unui element

priority_queue<T> H;
T v;
H.push(v);

Se adaugă în coadă elementul v. Elementele se reorganizează pentru se păstra proprietate de heap (elementul maxim să fie la început).

Ștergerea unui element

priority_queue<T> H;
H.pop();

Se șterge din coadă elementul de la început. Elementele se reorganizează pentru se păstra proprietate de heap.

Determinarea elementului din vârf

priority_queue<T> H;
T v;
v = H.top();

Returnează o referință la elementul de la începutul cozii. Elementul se va elimina numai la apelul metodei pop().

Stabilirea faptului că este coada vidă

priority_queue<T> H;
H.empty()

Returnează true dacă H este o coadă vidă și false în caz contrar.

Dimeniunea cozii

priority_queue<T> H;
H.size()

Returnează numărul de elemente din coada de priorități H.

Atribuirea

Conținutul unei cozi de priorități poate fi copiat în altă coadă de același tip prin operatorul de atribuire =.

priority_queue<T> A , B;
...
A = B;

Exemple

Considerăm următoarea problemă;

Se dau coordonatele întregi ale unor puncte în plan. Să se afișeze coordonatele în ordinea crescătoare a absciselor, iar la abscise egale în ordinea crescătoare a ordonatelor.

Următoarele soluții se bazează pe o coadă de priorități în care adăugăm toate punctele, apoi le extragem și le afișăm.

Soluția 1

Pentru memorarea unui punct folosim o structură (clasă) definită în mod adecvat. Pentru stabilirea ordinii între puncte folosim un functor, iar pentru afișarea coordonatelor folosim o funcție prietenă.

#include <iostream>
#include <queue>

using namespace std;

struct Punct{
	int x , y;
	Punct(int a = 0, int b = 0){ x  = a , y = b;}
	friend ostream & operator<<(ostream & os , Punct A)
	{
		os << "(" << A.x << "," << A.y << ")";
		return os;
	}
};

struct fcmp
{	bool operator()(const Punct & a , const Punct & b)
	{
		if(a.x > b.x)
			return true;
		if(a.x < b.x)
			return false;
		if(a.y > b.y)
			return true;
		return false;
	}
};

int main()
{
	priority_queue<Punct, vector<Punct>, fcmp> H;
	H.push(Punct(6,1));
	H.push(Punct(2,7));
	H.push(Punct(2,4));
	H.push(Punct(4,10));
	H.push(Punct(7,4));
	while(! H.empty())
		cout << H.top() << '\n', H.pop();
	return 0;
}

Soluția 2

În acestă soluție nu folosim un functor pentru comparare, ci supraîncărcăm operatorul < printr-o functie prietenă.

#include <iostream>
#include <queue>

using namespace std;

struct Punct{
	int x , y;
	Punct(int a = 0, int b = 0){ x  = a , y = b;}
	friend ostream & operator<<(ostream & os , const Punct & A)
	{
		os << "(" << A.x << "," << A.y << ")";
		return os;
	}
	friend bool operator<(const Punct & A , const Punct & B)
	{
		if(A.x > B.x)
			return true;
		if(A.x < B.x)
			return false;
		if(A.y > B.y)
			return true;
		return false;
	}
};

int main()
{
	priority_queue<Punct> H;
	H.push(Punct(6,1));
	H.push(Punct(2,7));
	H.push(Punct(2,4));
	H.push(Punct(4,10));
	H.push(Punct(7,4));
	while(! H.empty())
		cout << H.top() << '\n', H.pop();
	return 0;
}

Soluția 3

Pentru memorare punctelor folosim clasa pair. Clasa pair are definit operatorul mai mic, acesta verificând ordinea lexicografică pentru membrii first și second.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	priority_queue <
		pair<int,int>,
		vector<pair<int,int>>,
		greater<pair<int,int>>
		> H;
	H.push({6,1});
	H.push({2,7});
	H.push({2,4});
	H.push({4,10});
	H.push({7,4});
	while(! H.empty())
		cout << "(" << H.top().first << "," << H.top().second << ")" << '\n', H.pop();
	return 0;
}

Declararea de mai sus trebuie făcută în acest mod, pentru a obține un min-heap. Dacă am fi folosit declararea:

priority_queue <pair<int,int> > H;

s-ar fi implementat (pe baza functorului less<pair<int,int>>) un max-heap, în care elementele de prioritate maximă ar fi fost acela care au câmpul first mai mare.