h2(#stl). Alternative STL
Desi nu sunt greu de implementat, avem vesti bune pentru programatorii in C++: heap-urile sunt deja implementate in STL. Containerul se numeste 'priority_queue':http://www.sgi.com/tech/stl/priority_queue.html si implementeaza toate operatiile prezentate mai putin operatia de cautare a unei valori si de stergere a unui nod. Aceste doua operatii sunt destul de atipice pentru o coada de prioritati si in general nu sunt asociate cu aceasta structura de date in cartile de algoritmi.
Desi nu sunt greu de implementat, avem vesti bune pentru programatorii in C++: heap-urile sunt deja implementate in STL. Containerul se numeste '$priority_queue$':http://www.sgi.com/tech/stl/priority_queue.html si implementeaza toate operatiile prezentate, mai putin operatiile de cautare a unei valori si de stergere a unui nod. Aceste doua operatii sunt destul de atipice pentru o coada de prioritati si in general nu sunt asociate cu aceasta structura de date in cartile de algoritmi.
Totusi, in unele aplicatii avem nevoie de o structura de date care suporta toate operatiile amintite in timp cel mult logaritmic (inclusiv stergerea si cautarea unei valori). Aceasta structura exista deja in STL: $set$-urile. Acestea sunt de fapt multimi intretinute ca 'arbori binari echilibrati':arbori-binari-echilibrati. Singurul dejavantaj este ca de obicei merg mai incet decat cozile de prioritate si folosesc mai multa memorie.
Totusi, in unele aplicatii avem nevoie de o structura de date care suporta toate operatiile amintite in timp cel mult logaritmic (inclusiv stergerea si cautarea unei valori). Aceasta structura exista deja in STL: $set$-urile. Acestea sunt de fapt multimi intretinute ca arbori binari echilibrati. Singurul dezavantaj este ca de obicei merg mai incet decat cozile de prioritate si folosesc mai multa memorie.
Daca nu sunteti familiari cu aceste structuri de date, va recomandam sa cititi paginile lor de documentatie: 'priority_queue':http://www.sgi.com/tech/stl/priority_queue.html, 'set':http://www.sgi.com/tech/stl/set.html si 'multiset':http://www.sgi.com/tech/stl/multiset.html. Daca nu intelegeti totul de la inceput (pentru ca nu stiti clase si template-uri in C++), uitati-va pe exemple si pe lista de functii membre si invatati cum se folosesc.
Daca nu sunteti familiari cu aceste structuri de date, va recomandam sa cititi paginile lor de documentatie: '$priority_queue$':http://www.sgi.com/tech/stl/priority_queue.html, '$set$':http://www.sgi.com/tech/stl/set.html si '$multiset$':http://www.sgi.com/tech/stl/multiset.html. Daca nu intelegeti totul de la inceput (pentru ca nu stiti clase si template-uri in C++), uitati-va pe exemple si pe lista de functii membre si invatati cum se folosesc.
In continuare vom ilustra cum putem implementa operatiile de extragere a maximului, extragere a minimului, inserare, stergere si cautare folosind un $multiset$. Vom folosi un multiset pentru ca toate copiile unui numar vor fi pastrate daca el va fi inserat de mai multe ori (spre deosebire de set, care il va pastra o singura data). Va recomandam cu caldura sa copiati codul pe calculatorul vostru si sa experimentati cu el pentru a vedea ce afiseaza si a intelege ce se intampla.
In continuare vom ilustra cum putem implementa operatiile de extragere a maximului, extragere a minimului, inserare, stergere si cautare folosind un $multiset$. Vom folosi un multiset pentru ca toate copiile unui numar vor fi pastrate daca el va fi inserat de mai multe ori (spre deosebire de $set$, care il va pastra o singura data). Va recomandam cu caldura sa copiati codul pe calculatorul vostru si sa experimentati cu el pentru a vedea ce afiseaza si a intelege ce se intampla.
==code(cpp) |
#include <set>
