A C++-Prioritätswarteschlange ist eine Art Containeradapter, der speziell so konzipiert ist, dass das erste Element der Warteschlange entweder das größte oder das kleinste aller Elemente in der Warteschlange ist und die Elemente in nicht aufsteigender oder nicht absteigender Reihenfolge vorliegen (daher können wir sehen, dass jedes Element nicht auf- oder absteigend ist). Element der Warteschlange hat eine Priorität {feste Reihenfolge}).
In C++ STL ist das oberste Element standardmäßig immer das größte. Wir können es auch auf das kleinste Element oben ändern. Prioritätswarteschlangen werden oben auf dem maximalen Heap aufgebaut und verwenden ein Array oder einen Vektor als interne Struktur. In einfachen Worten, STL-Prioritätswarteschlange ist die Implementierung von 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;> }> |
>
>Ausgabe
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Max. Heap-Prioritätswarteschlange (Standardschema)
Wie erstelle ich einen Min-Heap für die Prioritätswarteschlange?
Wie wir zuvor gesehen haben, ist eine Prioritätswarteschlange in C++ standardmäßig als Max-Heap implementiert. Sie bietet uns jedoch auch die Möglichkeit, sie in Min-Heap zu ändern, indem wir beim Erstellen einer Prioritätswarteschlange einen weiteren Parameter übergeben.
Syntax:
priority_queue gq;>
Wo,
- „int“ ist der Elementtyp, den Sie in der Prioritätswarteschlange speichern möchten. In diesem Fall handelt es sich um eine ganze Zahl. Sie können ersetzen int mit jedem anderen Datentyp, den Sie benötigen. „Vektor“ ist die Art des internen Containers, der zum Speichern dieser Elemente verwendet wird. std::priority_queue ist kein Container an sich, sondern ein Containeranwender. Es umhüllt andere Behälter. In diesem Beispiel verwenden wir a Vektor , aber Sie könnten einen anderen Container wählen, der die Methoden front(), push_back() und pop_back() unterstützt.
- ' größer „ist eine benutzerdefinierte Vergleichsfunktion. Dies bestimmt, wie die Elemente innerhalb der Prioritätswarteschlange angeordnet sind. In diesem speziellen Beispiel richtet „größer“ a ein Min-Heap . Das bedeutet, dass das kleinste Element ganz oben in der Warteschlange steht.
Im Fall von „Max Heap“ mussten wir sie nicht angeben, da die Standardwerte für diese bereits für „Max Heap“ geeignet sind.
Beispiel:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, größer<>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 |
>
>Ausgabe
Volladdierer-Wahrheitstabelle
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Min. Heap-Prioritätswarteschlange
Notiz: Die obige Syntax ist möglicherweise schwer zu merken. Bei numerischen Werten können wir die Werte daher mit -1 multiplizieren und „Max Heap“ verwenden, um den Effekt von „Min Heap“ zu erzielen. Darüber hinaus können wir durch Ersetzen eine benutzerdefinierte Sortiermethode verwenden größer mit benutzerdefinierter Komparatorfunktion.
Methoden der Prioritätswarteschlange
Die folgende Liste aller Methoden der Klasse std::priority_queue:
| Methode | Definition |
|---|---|
| prioritätswarteschlange::empty() | Gibt zurück, ob die Warteschlange leer ist. |
| prioritätswarteschlange::size() | Gibt die Größe der Warteschlange zurück. |
| prioritätswarteschlange::top() | Gibt einen Verweis auf das oberste Element der Warteschlange zurück. |
| prioritätswarteschlange::push() | Fügt das Element „g“ am Ende der Warteschlange hinzu. |
| prioritätswarteschlange::pop() | Löscht das erste Element der Warteschlange. |
| prioritätswarteschlange::swap() | Wird zum Austauschen des Inhalts zweier Warteschlangen verwendet, sofern die Warteschlangen vom gleichen Typ sein müssen, obwohl die Größe unterschiedlich sein kann. |
| Priority_queue::emplace() | Wird verwendet, um ein neues Element in den Prioritätswarteschlangencontainer einzufügen. |
| Werttyp der Prioritätswarteschlange | Stellt den Objekttyp dar, der als Element in einer Priority_Queue gespeichert ist. Es fungiert als Synonym für den Vorlagenparameter. |
Operationen in der Prioritätswarteschlange in C++
1. Elemente einer Prioritätswarteschlange einfügen und entfernen
Der drücken() Die Methode wird verwendet, um ein Element in die Prioritätswarteschlange einzufügen. Um ein Element aus der Prioritätswarteschlange zu entfernen, müssen Sie Folgendes tun: Pop() Die Methode wird verwendet, da dadurch das Element mit der höchsten Priorität entfernt wird.
Nachfolgend finden Sie das C++-Programm für verschiedene Funktionen in der Prioritätswarteschlange:
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;> }> |
>
>Ausgabe
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Siehe Ende für Komplexitätsanalyse.
Notiz : Oben ist eine der Methoden zur Initialisierung der Prioritätswarteschlange dargestellt. Um mehr über die effiziente Initialisierung der Prioritätswarteschlange zu erfahren, klicken Sie hier.
2. Um auf das oberste Element der Prioritätswarteschlange zuzugreifen
Auf das oberste Element der Prioritätswarteschlange kann über zugegriffen werden Spitze() Methode.
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>>Zahlen;> >// 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;> }> |
>
>Ausgabe
Top element: 20>
Siehe Ende für Komplexitätsanalyse.
Notiz: Wir können nur auf das oberste Element in der Prioritätswarteschlange zugreifen.
3. So überprüfen Sie, ob die Prioritätswarteschlange leer ist oder nicht:
Wir verwenden die Methode empty(), um zu prüfen, ob die Priority_Queue leer ist. Diese Methode gibt Folgendes zurück:
- True – Wird zurückgegeben, wenn die Prioritätswarteschlange leer ist, und wird durch 1 dargestellt. False – Wird erzeugt, wenn die Prioritätswarteschlange nicht leer oder False ist, und wird durch 0 gekennzeichnet
Beispiel:
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;> }> |
>
.tif-Datei
>Ausgabe
Contains element or False>
Siehe Ende für Komplexitätsanalyse.
4. So erhalten/prüfen Sie die Größe der Prioritätswarteschlange
Es bestimmt die Größe einer Prioritätswarteschlange. In einfachen Worten, die Größe() Die Methode wird verwendet, um die Anzahl der in der Datei vorhandenen Elemente zu ermitteln Prioritätswarteschlange .
Nachfolgend finden Sie das C++-Programm zum Überprüfen der Größe der Prioritätswarteschlange:
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;> }> |
>
>Ausgabe
Size of the queue: 4>
Siehe Ende für Komplexitätsanalyse.
5. Um den Inhalt einer Prioritätswarteschlange mit einer anderen mit ähnlichem Typ auszutauschen
Tauschen() Die Funktion wird verwendet, um den Inhalt einer Prioritätswarteschlange mit einer anderen Prioritätswarteschlange desselben Typs und derselben oder einer anderen Größe auszutauschen.
Unten ist das C++-Programm zum Austauschen des Inhalts einer Prioritätswarteschlange mit einem anderen ähnlichen Typs:
C++
NFA-Beispiele
// 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> |
>
>Ausgabe
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>
Siehe Ende für Komplexitätsanalyse.
6. Um ein neues Element in den Prioritätswarteschlangencontainer einzufügen
Emplace() Mit der Funktion wird ein neues Element in den Prioritätswarteschlangencontainer eingefügt. Das neue Element wird entsprechend seiner Priorität zur Prioritätswarteschlange hinzugefügt. Es ähnelt dem Push-Betrieb. Der Unterschied besteht darin, dass die Operation emplace() unnötige Kopien des Objekts speichert.
Unten finden Sie das C++-Programm zum Einfügen eines neuen Elements in den Prioritätswarteschlangencontainer:
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> |
>
>Ausgabe
Priority Queue = 6 5 4 3 2 1>
Siehe Ende für Komplexitätsanalyse.
7. Zur Darstellung des Objekttyps, der als Element in einer Priority_Queue gespeichert ist
Die Methode „priority_queue :: value_type“ ist eine integrierte Funktion in C++ STL, die den Typ des Objekts darstellt, das als Element in einer „priority_queue“ gespeichert ist. Es fungiert als Synonym für den Vorlagenparameter.
Syntax:
priority_queue::value_type variable_name>
Unten ist das C++-Programm zur Darstellung des Objekttyps, der als Element in einer Priority_Queue gespeichert ist:
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> |
>
>Ausgabe
Algebra der Mengen
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>
Siehe Ende für Komplexitätsanalyse.
Komplexität aller Vorgänge:
| Methoden | Zeitkomplexität | Hilfsraum |
|---|---|---|
| prioritätswarteschlange::empty() | O(1) | O(1) |
| prioritätswarteschlange::size() | O(1) | O(1) |
| prioritätswarteschlange::top() | O(1) | O(1) |
| prioritätswarteschlange::push() | O(logN) | O(1) |
| prioritätswarteschlange::pop() | O(logN) | O(1) |
| prioritätswarteschlange::swap() | O(1) | AN) |
| Priority_queue::emplace() | O(logN) | O(1) |
| Werttyp der Prioritätswarteschlange | O(1) | O(1) |