4.1. Co to jest kolejka priorytetowa?
Kolejka priorytetowa jest to
struktura danych, w której dostęp do danych jest możliwy tylko do pierwszego elementu, a dane w niej są uporządkowane
nierosnąco (lub
niemalejąco). Kolejka priorytetowa jest określana mianem FIFO (First In First Out), czyli
pierwszy wchodzący element jest pierwszym wychodzącym.
4.1.1. Co to znaczy uporządkowanie nierosnące?
Uporządkowanie nierosnące jest to taki porządek danych, w którym
każda następna wartość jest
mniejsza lub równa od swojego poprzednika.
Przykładowy porządek liczb nierosnący:
50,40,40,39,30,18,18,2,1,1,0
4.1.2. Co to znaczy uporządkowanie niemalejące?
Uporządkowanie niemalejące jest to taki porządek danych, w którym
każda następna wartość jest
większa lub równa od swojego poprzednika.
Przykładowy porządek liczb niemalejący:
1,1,2,3,4,33,77,87,88,88,99
4.2. Operacje na kolejce priorytetowej
Kolejka priorytetowa w STL'u posiada następujące operacje:
4.3. Jak wykorzystywać adapter kolejki priorytetowej w C++
Aby móc skorzystać z kolejki priorytetowej w C++, należy dołączyć plik nagłówkowy:
Kolejnym krokiem, jaki musimy wykonać jest utworzenie kolejki priorytetowej. Zapis uogólniony wygląda tak:
std::priority_queue < TYP_DANYCH > nazwa_dla_kolejki_priorytetowej;
Kolejka priorytetowa może przechowywać dowolny typ danych - mogą być to typy, które już znasz czyli:
std::priority_queue < int > kolejka1;
std::priority_queue < std::string > kolejka2;
Kolejka priorytetowa umożliwia również przechowywanie własnych typów danych, takich jak struktury czy klasy. Nie jest to jednak już tak proste, jak w przypadku adaptera zwykłej kolejki czy też stosu. Aby mieć możliwość umieszczania własnych struktur danych w kolejce priorytetowej musimy poinformować adapter w jaki sposób dane powinny być porządkowane. Zagadnienie to zostanie omówione po przedstawieniu metod kontenera i sposobie korzystania z nich. Jedyne co warto teraz wiedzieć to fakt, że sposób korzystania z metod kolejki priorytetowej pozostanie
taki sam i praktycznie wogóle nie będzie wymagana ingerencja w kod poza wierszem w którym tworzysz kontener.
4.4. Umieszczanie nowego elementu w kolejce priorytetowej (metoda: push)
Metoda
push służy do umieszczenia nowego elementu na końcu kolejki priorytetowej.
void push( const TYP_DANYCH & wartosc );
Standardowa złożoność obliczeniowa metody:
O(log(n)).
4.4.1. Przykład
#include <queue>
int main()
{
std::priority_queue < int > kolejkaLiczb;
kolejkaLiczb.push( 123 );
kolejkaLiczb.push( 12 );
kolejkaLiczb.push( 55 );
return 0;
}
4.5. Odczytywanie pierwszego elementu w kolejce priorytetowej (metoda: top)
Metoda
top służy do odczytania wartości umieszczonej na początku kolejki priorytetowej. Modyfikacja wartości bezpośrednio nie jest możliwa.
const TYP_DANYCH & top();
Standardowo zwracana wartość:
największa.
Standardowa złożoność obliczeniowa metody:
O(1).
4.5.1. Przykład
#include <queue>
#include <iostream>
#include <conio.h>
int main()
{
std::priority_queue < int > kolejkaLiczb;
std::cout << "Podaj liczbe: ";
int liczba;
std::cin >> liczba;
kolejkaLiczb.push( liczba );
kolejkaLiczb.push( 222 );
kolejkaLiczb.push( 555 );
std::cout << "Pierwsza liczba w kolejce priorytetowej to: " << kolejkaLiczb.top() << std::endl;
kolejkaLiczb.push( kolejkaLiczb.top() + 55 );
std::cout << "Dodalem nowy element do kolejki priorytetowej." << std::endl;
std::cout << "Pierwsza liczba w kolejce priorytetowej to: " << kolejkaLiczb.top() << std::endl;
getch();
return 0;
}
4.6. Pobranie informacji o ilości elementów w kolejce priorytetowej (metoda: size)
Metoda
size zwraca ilość elementów aktualnie znajdujących się w kolejce priorytetowej.
size_type size() const;
Standardowa złożoność obliczeniowa metody:
O(1).
4.6.1. Przykład
#include <queue>
#include <iostream>
#include <conio.h>
int main()
{
std::priority_queue < int > kolejkaLiczb;
int liczba = 0;
do
{
std::cout << "Podaj liczbe (0 - konczy wprowadzanie liczb): ";
liczba = 0;
std::cin >> liczba;
if( liczba != 0 ) kolejkaLiczb.push( liczba );
} while( liczba != 0 );
std::cout << "W kolejce priorytetowej znajduje sie " << kolejkaLiczb.size() << " liczb." << std::endl;
getch();
return 0;
}
4.7. Sprawdzanie czy kolejka priorytetowa jest pusta (metoda: empty)
Metoda
empty sprawdza, czy kolejka priorytetowa jest pusta.
bool empty() const;
Standardowa złożoność obliczeniowa metody:
O(1).
4.7.1. Przykład
#include <queue>
#include <iostream>
#include <conio.h>
int main()
{
std::priority_queue < int > kolejkaLiczb;
if( kolejkaLiczb.empty() )
{
std::cout << "Kolejka jest pusta." << std::endl;
} else
{
std::cout << "W kolejce znajduje sie przynajmniej jeden element." << std::endl;
}
kolejkaLiczb.push( 1234 );
kolejkaLiczb.push( 124 );
kolejkaLiczb.push( 34 );
kolejkaLiczb.push( 4 );
if( kolejkaLiczb.empty() )
{
std::cout << "Kolejka jest pusta." << std::endl;
} else
{
std::cout << "W kolejce znajduje sie przynajmniej jeden element." << std::endl;
}
getch();
return 0;
}
4.8. Usunięcie istniejącego elementu z początku kolejki priorytetowej (metoda: pop)
Metoda
pop służy do usunięcia istniejącego elementu z początku kolejki priorytetowej.
void pop();
Standardowo usuwana wartość:
największa.
Standardowa złożoność obliczeniowa metody:
O(log(n)).
4.8.1. Przykład
#include <queue>
#include <iostream>
#include <conio.h>
int main()
{
std::queue < int > kolejkaLiczb;
int liczba = 0;
do
{
std::cout << "Podaj liczbe (0 - konczy wprowadzanie liczb): ";
liczba = 0;
std::cin >> liczba;
if( liczba != 0 ) kolejkaLiczb.push( liczba );
} while( liczba != 0 );
std::cout << "Liczby wyjete z kolejki: ";
while( kolejkaLiczb.empty() == false )
{
std::cout << kolejkaLiczb.front() << ", ";
kolejkaLiczb.pop();
}
getch();
return 0;
}
4.9. Ustawianie kierunku sortowania danych
Jeśli chcemy z góry określić kierunek sortowania dla danych lub poprostu go odwrócić możemy zrobić to w bardzo prosty sposób - wystarczy zmienić zapis tworzący kolejkę priorytetową na jeden z następujących:
std::priority_queue < int, std::vector < int >, std::less < int > > k1;
std::priority_queue < int, std::vector < int >, std::greater < int > > k2;
Ostatni parametr szablonu kolejki priorytetowej to
funktor, który określa sposób porównywania dwóch elementów w kolejce priorytetowej. STL posiada jeszcze parę innych funktorów do porównywania danych, jednak w przypadku kolejki priorytetowej zastosowanie ich byłoby bezsensowne.
4.10. Wykorzystywanie własnych typów danych w kolejce priorytetowej
Korzystanie z kolejki priorytetowej dla standardowych typów danych dostępnych w C++ jest bardzo proste, jednak znacznie częściej będziemy potrzebowali własnego typu danych, czyli struktury lub klasy. Załóżmy więc, że mamy następującą strukturę danych:
struct SOsoba
{
std::string imie;
std::string nazwisko;
int kolejnosc;
std::string inneDane;
};
Dla powyższej struktury danych utwórzmy teraz kontener na dane w oparciu o adaper kolejki priorytetowej:
std::priority_queue < SOsoba > kolejkaPriorytetowa;
Pomimo, iż powyższy zapis wydaje się oczywisty na bazie tego, co się do tej pory nauczyłeś kompilator zwróci nam następujące błędy kompilacji:
Kompilator: Default compiler
Wykonywanie g++.exe...
C:/Dev-Cpp/include/c++/3.4.2/bits/stl_function.h: In member function `bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = SOsoba]':
C:/Dev-Cpp/include/c++/3.4.2/bits/stl_heap.h:279: instantiated from `void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<SOsoba*, std::vector<SOsoba, std::allocator<SOsoba> > >, _Distance = int, _Tp = SOsoba, _Compare = std::less<SOsoba>]'
C:/Dev-Cpp/include/c++/3.4.2/bits/stl_heap.h:404: instantiated from `void std::make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<SOsoba*, std::vector<SOsoba, std::allocator<SOsoba> > >, _Compare = std::less<SOsoba>]'
C:/Dev-Cpp/include/c++/3.4.2/bits/stl_queue.h:369: instantiated from `std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&) [with _Tp = SOsoba, _Sequence = std::vector<SOsoba, std::allocator<SOsoba> >, _Compare = std::less<SOsoba>]'
D:/jakisPlik.cpp:12: instantiated from here
C:/Dev-Cpp/include/c++/3.4.2/bits/stl_function.h:227: error: no match for 'operator<' in '__x < __y'
Wykonanie zakończone
Możesz w tym miejscu zacząć się zastanawiać po co się uczyć kontenera w którym nie można własnego typu danych używać. Jeśli tak myślisz, to jesteś w błędzie. STL został zaprojektowany tak, aby był on zarówno wydajny jak i elastyczny.
4.10.1. Analizujemy przyczynę wystąpienia błędu
Chcąc zostać prawdziwym programistą nie możemy skupiać się tylko i wyłącznie na szukaniu gotowych rozwiązań problemów. Napotykając problemy musisz nauczyć się je analizować i szukać przyczyny błędu. Przeprowadźmy więc krótką analizę tego co wiemy i postawmy tyle pytań ile się da oraz udzielmy na nie odpowiedzi, jeśli są one oczywiste:
Dlaczego? Czym się one różnią te adaptery od siebie?
Dlaczego nie zaprojektowano tego adaptera, aby robił to za nas?
W tym momencie kończą się oczywiste wnioski dla osób, które nie mają dużego zasobu wiedzy z programowania i projektowania. Ważne jest jednak dokonywanie analizy każdego zagadnienia w którym napotykasz problemy - dzięki temu będziesz rozumiał lepiej to co robisz i w przyszłości będziesz miał większą wiedzę natrafiając na podobne problemy.
4.10.2. Kulisy powstawania STL'a
W czasach gdy STL powstawał projektanci STL'a nie byli w stanie stworzyć automatycznego mechanizmu, który umożliwiłby porządkowanie danych dla struktur o której nie mają praktycznie żadnych informacji. Co więcej do dnia dzisiejszego taki mechanizm prawdopodobnie nie istnieje,a przynajmniej nie jest mi znany i nie widzę możliwości wykonania takiego mechanizmu z dwóch względów:
Zważywszy na powyższe punkty staje się oczywiste, że wykonanie automatycznego mechanizmu jest praktycznie rzecz biorąc niemożliwe. Projektanci STL'a jednak mając ogromną wiedzę z dziedziny programowania i projektowania powiedzieli sobie:
skoro nie możemy utworzyć automatycznego mechanizmu sortowania, dajmy możliwość stworzenia go programiście w łatwy sposób. - i tak się stało.
4.10.3. Tworzymy własny funktor sortujący
Utworzenie funktora sortującego, z której STL będzie mógł korzystać jest bardzo proste. Zwróć jednak uwagę w jaki sposób zostało zaprogramowane sortowanie gdy mamy więcej niż jedną kolumnę. Jest to najprostszy sposób aby dane sortowały się
prawidłowo w kilku kolumnach i polecam go dobrze zapamiętać.
#include <string>
#include <queue>
struct SOsoba
{
std::string imie;
std::string nazwisko;
int kolejnosc;
std::string inneDane;
};
struct PorownajOsoby
{
bool operator ()( const SOsoba & osoba1, const SOsoba & osoba2 )
{
if( osoba1.kolejnosc > osoba2.kolejnosc ) return true;
if( osoba1.kolejnosc < osoba2.kolejnosc ) return false;
if( osoba1.nazwisko > osoba2.nazwisko ) return true;
if( osoba1.nazwisko < osoba2.nazwisko ) return false;
if( osoba1.nazwisko < osoba2.nazwisko ) return true;
if( osoba1.nazwisko > osoba2.nazwisko ) return false;
return false;
}
};
int main()
{
return 0;
}
Warto w tym miejscu również dodać, że kolumny których nie uwzględnimy w sortowaniu
nie będą umieszczone w kolejności w której zostały dodane. Kolumny te będą
na losowej pozycji. Warto tutaj też uściślić co to znaczy ta losowość - mianowicie dane zostaną posortowane wg. tych kolumn, które określiłeś, ale
nie możesz zakładać, że jeśli wszystkie kolumny będą miały takie same dane po których sortujesz, to kolejność elementów w kolejce priorytetowej nie będzie zmieniana. Uruchomienie przykładu, znajdującego się w dalszej części tej lekcji powinno ułatwić Ci zrozumienie powyższej treści.
4.10.4. Tworzymy działający adapter kolejki priorytetowej dla własnej struktury
Aby utworzyć sprawny adapter musimy ustawić dodatkowo dwa parametry szablonu:
std::priority_queue < , , > nazwa_kolejki_priorytetowej;
Inicjacja adaptera kolejki priorytetowej może więc wyglądać tak:
std::priority_queue < SOsoba, std::vector < SOsoba >, PorownajOsoby > kolejkaPriorytetowa;
4.10.5. Przykład
#include <iostream>
#include <string>
#include <queue>
#include <conio.h>
struct SOsoba
{
std::string imie;
std::string nazwisko;
int kolejnosc;
std::string inneDane;
};
struct PorownajOsoby
{
bool operator ()( const SOsoba & osoba1, const SOsoba & osoba2 )
{
if( osoba1.kolejnosc > osoba2.kolejnosc ) return true;
if( osoba1.kolejnosc < osoba2.kolejnosc ) return false;
if( osoba1.nazwisko > osoba2.nazwisko ) return true;
if( osoba1.nazwisko < osoba2.nazwisko ) return false;
if( osoba1.nazwisko < osoba2.nazwisko ) return true;
if( osoba1.nazwisko > osoba2.nazwisko ) return false;
return false;
}
};
typedef std::priority_queue < SOsoba, std::vector < SOsoba >, PorownajOsoby > TKolejkaPriorytetowaOsob;
void WstawOsobe( TKolejkaPriorytetowaOsob & kp, const char * imie, const char * nazwisko, int kolejnosc, const char * inneDane )
{
SOsoba nowaOsoba;
nowaOsoba.imie = imie;
nowaOsoba.nazwisko = nazwisko;
nowaOsoba.kolejnosc = kolejnosc;
nowaOsoba.inneDane = inneDane;
kp.push( nowaOsoba );
}
int main()
{
TKolejkaPriorytetowaOsob kolejkaPriorytetowa;
WstawOsobe( kolejkaPriorytetowa, "Imie", "Nazwisko", 1, "Pierwszy" );
WstawOsobe( kolejkaPriorytetowa, "Imie", "Nazwisko", 1, "Drugi" );
WstawOsobe( kolejkaPriorytetowa, "Imie", "Nazwisko", 1, "Trzeci" );
WstawOsobe( kolejkaPriorytetowa, "Imie", "Ziomek", 1, "Czwarty" );
while( kolejkaPriorytetowa.size() > 0 )
{
SOsoba odczytana = kolejkaPriorytetowa.top();
kolejkaPriorytetowa.pop();
std::cout << odczytana.imie << "; " << odczytana.nazwisko << "; " << odczytana.kolejnosc << "; " << odczytana.inneDane << "; " << std::endl;
}
getch();
return 0;
}
4.11. Zaawansowane wykorzystywanie adaptera kolejki
Jak zapewne zauważyłeś do tej pory omówiliśmy pierwszy i trzeci parametr adaptera kolejki priorytetowej. W tym podrozdziale skoncentrujemy się na drugim. Zanim jednak do niego przejdziemy warto jeszcze wspomnieć o tym jak jest zdefiniowany adapter kolejki priorytetowej w STL'u.
namespace std
{
template < typename typZmiennej, typename kontenerDanych, typename funktorPorownania >
class priority_queue
{
};
}
Aby adapter kolejki priorytetowej był łatwy w użyciu dla stadrardowych typów danych, twórcy STL'a dopisali jeszcze linijkę:
template < typename typZmiennej, typename kontenerDanych = vector < typZmiennej >, typename funktorPorownania = less < typZmiennej > >
class priority_queue;
Dzięki powyższemu zapisowi kompilator wie, że jeśli nie podamy drugiego i trzeciego parametru, to użyje on domyślnego kontenera i domyślnego funktora. Zgodnie z powyższym - poniższe dwa zapisy są sobie równoważne:
std::priority_queue < int > mojaKolejka1;
std::priority_queue < int, std::vector < int >, std::less < int > > mojaKolejka2;