Kolejka priorytetowa w standardowej bibliotece szablonów C++ (STL)
A Kolejka priorytetowa C++ to rodzaj adaptera kontenera, specjalnie zaprojektowanego w taki sposób, że pierwszy element kolejki jest albo największym, albo najmniejszym ze wszystkich elementów w kolejce, a elementy są ułożone w kolejności nierosnącej lub niemalejącej (stąd widzimy, że każdy element kolejki ma priorytet {stała kolejność}).
W C++ STL domyślnie najwyższy element jest zawsze największy. Możemy go także zmienić na najmniejszy element u góry. Kolejki priorytetowe są budowane na szczycie sterty maksymalnej i wykorzystują tablicę lub wektor jako strukturę wewnętrzną. W prostych słowach, Kolejka priorytetowa STL jest implementacją C++
// C++ program to demonstrate the use of priority_queue> #include> #include> using> namespace> std;> // driver code> int> main()> {> > int> arr[6] = { 10, 2, 4, 8, 6, 9 };> > // defining priority queue> > priority_queue <> int> >pq;> > // printing array> > cout < <> 'Array: '> ;> > for> (> auto> i : arr) {> > cout < < i < <> ' '> ;> > }> > cout < < endl;> > // pushing array sequentially one by one> > for> (> int> i = 0; i <6; i++) {> > pq.push(arr[i]);> > }> > // printing priority queue> > cout < <> 'Priority Queue: '> ;> > while> (!pq.empty()) {> > cout < < pq.top() < <> ' '> ;> > pq.pop();> > }> > return> 0;> }> |
Wyjście
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2
Kolejka priorytetowa maks. sterty (schemat domyślny)
Jak utworzyć stertę minimalną dla kolejki priorytetowej?
Jak widzieliśmy wcześniej, kolejka priorytetowa jest domyślnie zaimplementowana w C++ jako sterta maksymalna, ale zapewnia nam również opcję zmiany jej na stertę minimalną poprzez przekazanie innego parametru podczas tworzenia kolejki priorytetowej.
Składnia:
priority_queue gq;
Gdzie,
- „int” to typ elementów, które chcesz przechowywać w kolejce priorytetowej. W tym przypadku jest to liczba całkowita. Możesz wymienić wew z dowolnym innym typem danych, którego potrzebujesz. „wektor” to rodzaj wewnętrznego pojemnika używanego do przechowywania tych elementów. std::priority_queue nie jest kontenerem samym w sobie, ale podmiotem przyjmującym kontener. Owija inne pojemniki. W tym przykładzie używamy a wektor , ale możesz wybrać inny kontener obsługujący metody front(), push_back() i pop_back().
- ' większy ' to niestandardowa funkcja porównania. Określa to sposób uporządkowania elementów w kolejce priorytetowej. W tym konkretnym przykładzie większe konfiguruje a min-kupa . Oznacza to, że najmniejszy element będzie na górze kolejki.
W przypadku maksymalnej sterty nie musieliśmy ich określać, ponieważ wartości domyślne są już odpowiednie dla maksymalnej sterty.
Przykład:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> > priority_queue <> int> , vector <> int> >, większy <> int> >> g)> {> > while> (!g.empty()) {> > cout < <> ' '> < < g.top();> > g.pop();> > }> > cout < <> '
'> ;> }> void> showArray(> int> * arr,> int> n)> {> > for> (> int> i = 0; i cout < < arr[i] < < ' '; } cout < < endl; } // Driver Code int main() { int arr[6] = { 10, 2, 4, 8, 6, 9 }; priority_queue |
Wyjście
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10
Kolejka priorytetowa minimalnej sterty
Notatka: Powyższa składnia może być trudna do zapamiętania, dlatego w przypadku wartości liczbowych możemy pomnożyć wartości przez -1 i użyć maksymalnej sterty, aby uzyskać efekt minimalnej sterty. Nie tylko to, że możemy zastosować niestandardową metodę sortowania poprzez zamianę większy z niestandardową funkcją komparatora.
Metody kolejki priorytetowej
Poniższa lista wszystkich metod klasy std::priority_queue:
| metoda | Definicja |
|---|---|
| kolejka_priorytetu::pusta() | Zwraca informację, czy kolejka jest pusta. |
| kolejka_priorytetu::rozmiar() | Zwraca rozmiar kolejki. |
| kolejka_priorytetu::top() | Zwraca odwołanie do najwyższego elementu kolejki. |
| kolejka_priorytetu::push() | Dodaje element „g” na końcu kolejki. |
| kolejka_priorytetu::pop() | Usuwa pierwszy element kolejki. |
| kolejka_priorytetów::swap() | Służy do zamiany zawartości dwóch kolejek, pod warunkiem, że kolejki muszą być tego samego typu, chociaż rozmiary mogą się różnić. |
| kolejka_priorytetu::emplace() | Służy do wstawiania nowego elementu do kontenera kolejki priorytetowej. |
| kolejka_priorytetu typ_wartości | Reprezentuje typ obiektu przechowywanego jako element w kolejce priorytetowej. Działa jako synonim parametru szablonu. |
Operacje na kolejce priorytetowej w C++
1. Wstawianie i usuwanie elementów kolejki priorytetowej
The naciskać() metoda służy do wstawienia elementu do kolejki priorytetowej. Aby usunąć element z kolejki priorytetowej, należy wykonać polecenie Muzyka pop() Metoda jest używana, ponieważ usuwa element o najwyższym priorytecie.
Poniżej znajduje się program C++ dla różnych funkcji w kolejce priorytetowej:
C++
// C++ Program to demonstrate various> // method/function in Priority Queue> #include> #include> using> namespace> std;> // Implementation of priority queue> void> showpq(priority_queue <> int> >gq)> {> > priority_queue <> int> >g = gq;> > while> (!g.empty()) {> > cout < <> ' '> < < g.top();> > g.pop();> > }> > cout < <> '
'> ;> }> // Driver Code> int> main()> {> > priority_queue <> int> >gquiz;> > // used in inserting the element> > gquiz.push(10);> > gquiz.push(30);> > gquiz.push(20);> > gquiz.push(5);> > gquiz.push(1);> > cout < <> 'The priority queue gquiz is : '> ;> > > // used for highlighting the element> > showpq(gquiz);> > // used for identifying the size> > // of the priority queue> > cout < <> '
gquiz.size() : '> < <> > gquiz.size();> > // used for telling the top element> > // in priority queue> > cout < <> '
gquiz.top() : '> < <> > gquiz.top();> > // used for popping the element> > // from a priority queue> > cout < <> '
gquiz.pop() : '> ;> > gquiz.pop();> > showpq(gquiz);> > return> 0;> }> |
Wyjście
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1
Zapoznaj się z końcem analizy złożoności.
Notatka : Powyżej pokazano jedną z metod inicjalizacji kolejki priorytetowej. Aby dowiedzieć się więcej o sprawnej inicjalizacji kolejki priorytetowej kliknij tutaj.
2. Aby uzyskać dostęp do najwyższego elementu kolejki priorytetowej
Dostęp do najwyższego elementu kolejki priorytetowej można uzyskać za pomocą szczyt() metoda.
C++
// C++ program to access the top> // element of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> > // create a priority queue of int> > priority_queue <> int> >liczby;> > // add items to priority_queue> > numbers.push(1);> > numbers.push(20);> > numbers.push(7);> > // get the element at the top> > cout < <> 'Top element: '> < <> > numbers.top();> > return> 0;> }> |
Wyjście
Top element: 20
Zapoznaj się z końcem analizy złożoności.
Notatka: Możemy uzyskać dostęp tylko do najwyższego elementu w kolejce priorytetowej.
3. Aby sprawdzić, czy kolejka priorytetowa jest pusta, czy nie:
Używamy metody pusty(), aby sprawdzić, czy kolejka priorytetowa jest pusta. Ta metoda zwraca:
- True – Zwracany, gdy kolejka priorytetowa jest pusta i jest reprezentowany przez 1 False – Jest generowany, gdy kolejka priorytetowa nie jest pusta lub False i charakteryzuje się 0
Przykład:
C++
// C++ program to demonstrate> // Implementation of empty() function> #include> #include> using> namespace> std;> // Driver code> int> main()> {> > priority_queue <> int> >pqueueGFG;> > pqueueGFG.push(1);> > > // Priority Queue becomes 1> > // check if it is empty or not> > if> (pqueueGFG.empty())> > {> > cout < <> 'Empty or true'> ;> > }> > else> > {> > cout < <> 'Contains element or False'> ;> > }> > return> 0;> }> |
Wyjście
Contains element or False
Zapoznaj się z końcem analizy złożoności.
4. Aby uzyskać/sprawdzić rozmiar kolejki priorytetowej
Określa rozmiar kolejki priorytetowej. Mówiąc najprościej, rozmiar() metoda służy do uzyskania liczby elementów obecnych w pliku Kolejka priorytetowa .
Poniżej znajduje się program C++ sprawdzający wielkość kolejki priorytetowej:
C++
// C++ program to demonstrate the> // size() method of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> > // create a priority queue of string> > priority_queue pqueue;> > // add items to priority_queue> > pqueue.push(> 'Geeks'> );> > pqueue.push(> 'for'> );> > pqueue.push(> 'Geeks'> );> > pqueue.push(> 'C++'> );> > // get the size of queue> > int> size = pqueue.size();> > cout < <> 'Size of the queue: '> < < size;> > return> 0;> }> |
Wyjście
Size of the queue: 4
Zapoznaj się z końcem analizy złożoności.
5. Aby zamienić zawartość kolejki priorytetowej na inną kolejkę podobnego typu
Zamieniać() funkcja służy do zamiany zawartości jednej kolejki priorytetowej na inną kolejkę priorytetową tego samego typu i tego samego lub innego rozmiaru.
Poniżej znajduje się program C++ służący do zamiany zawartości kolejki priorytetowej na inną kolejkę podobnego typu:
C++
// CPP program to illustrate> // Implementation of swap() function> #include> using> namespace> std;> // Print elements of priority queue> void> print(priority_queue <> int> >pq)> {> > while> (!pq.empty()) {> > cout < < pq.top() < <> ' '> ;> > pq.pop();> > }> > cout < < endl;> }> int> main()> {> > // priority_queue container declaration> > priority_queue <> int> >pq1;> > priority_queue <> int> >pq2;> > // pushing elements into the 1st priority queue> > pq1.push(1);> > pq1.push(2);> > pq1.push(3);> > pq1.push(4);> > // pushing elements into the 2nd priority queue> > pq2.push(3);> > pq2.push(5);> > pq2.push(7);> > pq2.push(9);> > cout < <> 'Before swapping:-'> < < endl;> > cout < <> 'Priority Queue 1 = '> ;> > print(pq1);> > cout < <> 'Priority Queue 2 = '> ;> > print(pq2);> > // using swap() function to swap elements of priority> > // queues> > pq1.swap(pq2);> > cout < < endl < <> 'After swapping:-'> < < endl;> > cout < <> 'Priority Queue 1 = '> ;> > print(pq1);> > cout < <> 'Priority Queue 2 = '> ;> > print(pq2);> > return> 0;> }> // This code is contributed by Susobhan Akhuli> |
Wyjście
Before swapping:- Priority Queue 1 = 4 3 2 1 Priority Queue 2 = 9 7 5 3 After swapping:- Priority Queue 1 = 9 7 5 3 Priority Queue 2 = 4 3 2 1
Zapoznaj się z końcem analizy złożoności.
6. Aby umieścić nowy element w kontenerze kolejki priorytetowej
Umieścić() funkcja służy do wstawienia nowego elementu do kontenera kolejki priorytetowej, nowy element jest dodawany do kolejki priorytetowej zgodnie z jego priorytetem. Jest to podobne do operacji push. Różnica polega na tym, że operacja emplace() oszczędza niepotrzebną kopię obiektu.
Poniżej znajduje się program C++ służący do umieszczenia nowego elementu w kontenerze kolejki priorytetowej:
C++
// CPP program to illustrate> // Implementation of emplace() function> #include> using> namespace> std;> int> main()> {> > priority_queue <> int> >pq;> > pq.emplace(1);> > pq.emplace(2);> > pq.emplace(3);> > pq.emplace(4);> > pq.emplace(5);> > pq.emplace(6);> > // Priority queue becomes 1, 2, 3, 4, 5, 6> > // Printing the priority queue> > cout < <> 'Priority Queue = '> ;> > while> (!pq.empty()) {> > cout < < pq.top() < <> ' '> ;> > pq.pop();> > }> > return> 0;> }> // This code is contributed by Susobhan Akhuli> |
Wyjście
Priority Queue = 6 5 4 3 2 1
Zapoznaj się z końcem analizy złożoności.
7. Aby reprezentować typ obiektu przechowywanego jako element w kolejce priorytetowej
Metodapriorytet_queue ::value_type jest wbudowaną funkcją w języku C++ STL, która reprezentuje typ obiektu przechowywanego jako element w kolejce priorytetowej. Działa jako synonim parametru szablonu.
Składnia:
priority_queue::value_type variable_name
Poniżej znajduje się program C++ reprezentujący typ obiektu przechowywanego jako element w kolejce priorytetowej:
C++
// C++ program to illustrate the> // priority_queue :: value_type function> #include> using> namespace> std;> // Driver code> int> main()> {> > // declare integer value_type for priority queue> > priority_queue <> int> >::value_type AnInt;> > // declare string value_type for priority queue> > priority_queue::value_type AString;> > // Declares priority_queues> > priority_queue <> int> >q1;> > priority_queue q2;> > // Here AnInt acts as a variable of int data type> > AnInt = 20;> > cout < <> 'The value_type is AnInt = '> < < AnInt < < endl;> > q1.push(AnInt);> > AnInt = 30;> > q1.push(AnInt);> > cout < <> 'Top element of the integer priority_queue is: '> > < < q1.top() < < endl;> > // here AString acts as a variable of string data type> > AString => 'geek'> ;> > cout < < endl> > < <> 'The value_type is AString = '> < < AString> > < < endl;> > q2.push(AString);> > AString => 'for'> ;> > q2.push(AString);> > AString => 'geeks'> ;> > q2.push(AString);> > cout < <> 'Top element of the string priority_queue is: '> > < < q2.top() < < endl;> > return> 0;> }> // This code is contributed by Susobhan Akhuli> |
Wyjście
The value_type is AnInt = 20 Top element of the integer priority_queue is: 30 The value_type is AString = geek Top element of the string priority_queue is: geeks
Zapoznaj się z końcem analizy złożoności.
Złożoność wszystkich operacji:
| Metody | Złożoność czasu | Przestrzeń pomocnicza |
|---|---|---|
| kolejka_priorytetu::pusta() | O(1) | O(1) |
| kolejka_priorytetu::rozmiar() | O(1) | O(1) |
| kolejka_priorytetów::top() | O(1) | O(1) |
| kolejka_priorytetu::push() | O(logN) | O(1) |
| kolejka_priorytetów::pop() | O(logN) | O(1) |
| kolejka_priorytetów::swap() | O(1) | NA) |
| kolejka_priorytetu::emplace() | O(logN) | O(1) |
| kolejka_priorytetu typ_wartości | O(1) | O(1) |
