*TODO*: HEAP-uri implementate de mana VS priority_queue<> VS set<>
Desi nu sunt greu de implementat, avem vesti bune pentru programatorii in C++. In STL, cozile de prioritate (adica max-heap-urile) sunt deja implementate. Totusi, priority_queue nu este in standard-ul STL, aceasta inseamnand ca nu vor fi gasite neaparat in toate implementarile STL. Desi asta reprezinta un risc (e posibil sa nu gasitit priority_queue pe calculatoarele de la concurs) acesta esta minin.
Desi nu sunt greu de implementat, avem vesti bune pentru programatorii in C++. In STL, cozile de prioritate (adica max-heap-urile) sunt deja implementate. Totusi, mentionam ca priority_queue nu este in standard-ul STL, aceasta inseamnand ca nu vor fi gasite neaparat in toate implementarile STL. Desi asta reprezinta un risc (e posibil sa nu gasitit priority_queue pe calculatoarele de la concurs) acesta esta minin.
O alternativa la priority_queue-uri sunt set-urile si multiset-urile din STL. Acestea au doua avantaje: sunt in standard STL (deci nu riscati nimic) si pot efectua si cautari in O(logN) fiindca sunt implementate ca 'arbori binari echilibrati':arbori-binari-echilibrati.
O alternativa la priority_queue-uri sunt set-urile si multiset-urile din STL. Acestea au doua avantaje: sunt in standard STL (deci nu riscati nimic) si pot efectua si cautari in O(logN) fiindca sunt implementate ca 'arbori binari echilibrati':arbori-binari-echilibrati. Totusi avantajele vin cu un cost: set-urile si multiset-urile pot fi mai incete decat cozile de prioritate.
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 chiar tot de la inceput (pentru ca nu stiti clase si template-uri in C++), uitati-va pe exemple si pe lista de functii membre.
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 chiar tot 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 multi_set. 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).
In continuare vom ilustra cum putem implementa operatiile de extragere a maximului, extragere a minimului, inserare, stergere si cautare folosind un $multi_set$. 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).
h2(#aplicatii). Aplicatii
