priority queue verständnis



  • hallo zusammen,
    kann mir jemand die Funktionsweise der priority queue innerhalb der STL erklären? Mir ist nicht klar, wie dieser container erkennt welcher Wert die höchste Priorität hat und so beispielsweise einen Vector<int> absteigend sortieren kann.

    ich habe hier mal ein Beispielcode

    #include <iostream>
    #include <vector>
    #include <queue>
    
    int main() {
    	using namespace std;
    	vector<int> V{ 9,17,4,68,9,1,12,38,29 };
    	priority_queue<int> pq;
    
    	for (int i = 0; i < V.size(); i++) {
    		pq.push(V.at(i));
    	}
    	
    	for (int j = pq.size(); j > 0; j--) {
    		cout << pq.top() << endl;
    		pq.pop();
    	}
    	system("pause");
    	return 0;
    }
    

    gibt den Vector sortiert in absteigender Reihenfolge aus..
    Vor allem stellt sich mir dabei die Frage: wie effizient ist die Laufzeit des Sortierens gegenüber beispielsweise einem QuickSort algo?

    Und ist es Möglich die Reihenfolge umzukehren sodass der schlüssel mit der niedrigsten prio als erstes ausgegeben wird?

    Habe schon recherchiert aber keine für mich schlüssigen Antworten gefunden..



  • @WillyWilson
    Üblicherweise setzt die STL zum Vergleichen die Funktion std::less ein, um zwei Werte/Objekte miteinander zu vergleichen. Für numerische Datentypen ist das quasi immer definiert und für Werte- oder Stringtypen aus der STL auch. Wenn du eigene Datentypen verwendest musst du entweder den bool operator<() für deinen Datentypen überladen oder der priority_queue ein Vergleichsfunktion/-funktor mitgeben.

    Nachtrag:
    Soweit ich weiß sortiert die priority_queue nicht, sondern fügt Elemente an der passenden Stelle ein. Da die Queue sortiert ist passiert das mit O(log n). Ist quasi mit Insertion Sort zu vergleichen, nur dass nicht die ganze Queue sortiert wird, sondern nur neue Elemente eingefügt werden.

    Nachtrag 2:
    Mit

    #include <vector>
    #include <queue>
    #include <algorithm>
    #include <iostream>
    
    int main()
    {
        using pqg = std::priority_queue<int,std::vector<int>,std::greater<int>>;
        pqg queue;
        
        queue.push( 3 );
        queue.push( 1 );
        queue.push( 2 );
        queue.push( 4 );
        
        while( !queue.empty() )
        {
            std::cout << queue.top() << " ";
            queue.pop();
        }
        std::cout << "\nDone.\n";
    }
    

    hast du dein gewünschtes Verhalten.


  • Mod

    Die Queue selbst muss nicht sortiert sein (sie braucht nicht einmal das Konzept einer "Reihenfolge" ihrer Elemente haben), sie muss nur die Anforderung erfüllen, dass das Element mit der höchsten Priorität an erster Stelle steht (was auch immer genau die "erste" Stelle in der unterliegenden Datenstruktur ist) und muss diese Eigenschaft wieder herstellen, wenn das erste Element entfernt wird. Das heißt, das Entfernen des ersten Elements kann durchaus eine nicht-triviale Operation sein. Und wird es bei üblichen Implementierungen auch sein.

    Wenn du also Sortieralgorithmen mit Priority Queues vergleichen möchtest, dann musst du den Gesamtvorgang betrachten, Einfügen aller Elemente in die Queue und wieder herausholen. Und wenn du das tust, dann sind Sortieralgorithmen und Priority Queues im informatischen Sinne äquivalent. Tatsächlich ist eine beliebte Datenstruktur, um Priority Queues zu implementieren, der sogenannte 'Heap', und nicht ganz unzufällig ist 'Heapsort' ein beliebtes und effizientes Sortierverfahren.

    Das heißt aber auch - wie könnte es auch anders sein - dass es da keinen magischen Trick gibt, um die Komplexität von Sortierverfahren mit Priority Queues zu umgehen, oder um Priority Queues besonders effizient mittels guter Sortierverfahren zu implementieren. Die Grundschwierigkeit von Sortierung bleibt erhalten, egal wie herum man es dreht.



  • @DocShoe sagte in priority queue verständnis:

    Soweit ich weiß sortiert die priority_queue nicht, sondern fügt Elemente an der passenden Stelle ein.

    das ist mir irgendwie unbegreiflich.. wie soll es denn möglich sein etwas an einer passenden stelle einzufügen ohne das einzufügende element vorher mit dem rest der queue zu vergleichen? ich hätte gerne eine schritt-für-schritt visualisierung der pq funktion aber die scheint es nicht zu geben. Durch den debugger werde ich auch nicht schlauer. Schade, vielleicht bin ich einfach zu dumm um es zu verstehen 😃

    @SeppJ ist jede priorityqueue somit auch ein MaxHeap??



  • Noch als Antwort zur Frage, woher die pq weiß, wie sie sortieren soll: schau dir https://en.cppreference.com/w/cpp/container/priority_queue an.
    Der dritte Template-Parameter ist zur Sortierung da. Und steht standardmäßig, wie @DocShoe schrieb, auf std::less<T>. Wenn du da z.B. bei dir std::greater<int> einsetzt, würde die pq andersrum sortieren.



  • Wiee SeppJ schon schrieb ist nicht die Implementierung durch den Standard vorgeschrieben, sondern das Verhalten. Durch den zweiten Template Parameter wird der zu Grunde liegende Container spezifiziert, was per default std::vector ist. Da liegt die Vermutung schon nahe, dass die priority_queue eine Sortierung durch Einfügen an der passenden Stelle einhält. Vermutlich haben wir auch unterschiedliche Vorstellungen davon, was du mit Sortieren meinst. Für mich ist Sortieren das Sortieren eines ganzen Containers mit allen Elementen. Das ist bei einer priority_queue nicht zwingend notwendig, wenn man eine Einfügeposition bestimmen kann, die die Reihenfolge nicht bricht, ist das kein Sortieren für mich, sondern lediglich ein Einfügen eines Elementes an einer Stelle, sodass die Sortierreihenfolge nicht gebrochen wird.



  • @DocShoe sagte in priority queue verständnis:

    Wiee SeppJ schon schrieb ist nicht die Implementierung durch den Standard vorgeschrieben, sondern das Verhalten. Durch den zweiten Template Parameter wird der zu Grunde liegende Container spezifiziert, was per default std::vector ist. Da liegt die Vermutung schon nahe, dass die priority_queue eine Sortierung durch Einfügen an der passenden Stelle einhält. Vermutlich haben wir auch unterschiedliche Vorstellungen davon, was du mit Sortieren meinst. Für mich ist Sortieren das Sortieren eines ganzen Containers mit allen Elementen. Das ist bei einer priority_queue nicht zwingend notwendig, wenn man eine Einfügeposition bestimmen kann, die die Reihenfolge nicht bricht, ist das kein Sortieren für mich, sondern lediglich ein Einfügen eines Elementes an einer Stelle, sodass die Sortierreihenfolge nicht gebrochen wird.

    das könnte man so sehen, ja. Dann würdest du also jedes mal wenn du Karten spielst und deine Handkarten "sortierst" in wahrheit gar nicht sortieren, sondern nur die Karte an der richtigen Position einsetzen 😱 🤯

    aber die reihenfolge (von links nach rechts oder umgekehrt oder eben von oben nach unten oder umgekehrt) wird gezwungenermaßen immer geändert wenn man etwas an einer bestimmten stelle einfügt oder entfernt

    wie dem auch sei. Danke an @wob der Link ist sehr hilfreich und die erklärung für mich schlüssig



  • @WillyWilson sagte in priority queue verständnis:

    das könnte man so sehen, ja. Dann würdest du also jedes mal wenn du Karten spielst und deine Handkarten "sortierst" in wahrheit gar nicht sortieren, sondern nur die Karte an der richtigen Position einsetzen 😱 🤯

    Wenn ich die Karten einzeln aufnehme: Ja


  • Mod

    @WillyWilson sagte in priority queue verständnis:

    @DocShoe sagte in priority queue verständnis:

    Soweit ich weiß sortiert die priority_queue nicht, sondern fügt Elemente an der passenden Stelle ein.

    das ist mir irgendwie unbegreiflich.. wie soll es denn möglich sein etwas an einer passenden stelle einzufügen ohne das einzufügende element vorher mit dem rest der queue zu vergleichen? ich hätte gerne eine schritt-für-schritt visualisierung der pq funktion aber die scheint es nicht zu geben. Durch den debugger werde ich auch nicht schlauer. Schade, vielleicht bin ich einfach zu dumm um es zu verstehen 😃

    1. Wie schon gesagt, ist eine priority queue nicht zwangsläufig sortiert. Sie braucht nicht einmal so etwas wie eine "Reihenfolge" zu haben. Der MaxHeap (siehe unten) hat keine Reihenfolge. Er hat nur eine Spitze. Erst wenn man die derzeitige Spitze entfernt, weiß man, was die neue Spitze ist. vorher kann man nicht sagen, welches das "zweite" Element ist.
    2. Es gibt aber schon Container, die immer sortiert sind. Wie die das machen können (aber nicht müssen, es gibt auch andere Strategien) ist : Man weiß ja schon, dass das was man bisher hat, schon sortiert ist. Dann fängt man einfach in der Mitte an: Wenn das neue Element größer ist als das Element in der Mitte, dann muss es in der größeren Hälfte einsortiert werden; und umgekehrt, wenn es kleiner ist. Nehmen wir mal o.B.d.A. an, dass es größer ist. Dann guckt man sich die größere Hälfte der bisherigen Elemente an. die ist aber auch schon sortiert. Daher reicht es, sich das mittlere Element der größeren Hälfte anzugucken, und das neue Element damit zu vergleichen. Und somit weiß man dann wieder, ob man in dem kleineren oder dem größeren Viertel dieser Hälfte weiter machen muss. Und so fährt man fort, bis es nur noch einen Ort geben kann, wo das neue Element eingefügt werden kann.
      So kommt man mit relativ wenigen Vergleichen aus, um das neue Element einzufügen. Genauer gesagt, braucht man nur rund log_2(N)-Vergleiche, wobei N die Anzahl der Elemente ist, die schon in der Datenstruktur sind. Man braucht N solcher Einfügeaktionen, um eine sortierte Struktur der Größe N zu bauen, insgesamt also so grob N*log(N) Vergleiche. Und das ist dann - ohne Zufall - auch genau die Anzahl von Vergleichen, die übliche Sortieralgorithmen brauchen, um eine Menge zu sortieren.

    @SeppJ ist jede priorityqueue somit auch ein MaxHeap??

    Nein, aber ein MaxHeap ist eine gute und übliche Möglichkeit, eine PriorityQueue zu bauen.



  • @SeppJ sagte in priority queue verständnis:

    Wie schon gesagt, ist eine priority queue nicht zwangsläufig sortiert. Sie braucht nicht einmal so etwas wie eine "Reihenfolge" zu haben. Der MaxHeap (siehe unten) hat keine Reihenfolge. Er hat nur eine Spitze. Erst wenn man die derzeitige Spitze entfernt, weiß man, was die neue Spitze ist. vorher kann man nicht sagen, welches das "zweite" Element ist.

    das würde bedeuten, nach jedem pop() wird der gesamte Heap (also alle Elemente) erneut geprüft und miteinander verglichen?

    @DocShoe
    hab es mal vereinfacht, weiß nicht wieso du <algorithm> einbindest und wofür pqg sein soll wenn es auch so geht:

    #include <iostream>
    #include <vector>
    #include <queue>
    
    int main() {
    	using namespace std;
    	
    	priority_queue<int, vector<int>, greater<int>> queue_greater;
    	priority_queue<int> queue_lesser;
    	vector<int> V{ 9,17,4,68,9,1,12,38,29 };
    
    	for (int i = 0; i < V.size(); i++) 
    		queue_greater.push(V.at(i));
    	
    
    	for (int i = 0; i < V.size(); i++)
    		queue_lesser.push(V.at(i));
    	
    	cout << "Aufsteigend: ";
    	for (int j = queue_greater.size(); j > 0; j--) {
    		cout << queue_greater.top() << " ";
    		queue_greater.pop();
    	}
    
    	cout << endl << "Absteigend: ";
    	for (int j = queue_lesser.size(); j > 0; j--) {
    		cout << queue_lesser.top() << " ";
    		queue_lesser.pop();
    	}
    
    	cout << endl;
    	system("pause");
    	return 0;
    }
    

    sollte irgendwas an diesem code falsch oder blöd sein bitte bescheid geben


  • Mod

    @WillyWilson sagte in priority queue verständnis:

    @SeppJ sagte in priority queue verständnis:

    Wie schon gesagt, ist eine priority queue nicht zwangsläufig sortiert. Sie braucht nicht einmal so etwas wie eine "Reihenfolge" zu haben. Der MaxHeap (siehe unten) hat keine Reihenfolge. Er hat nur eine Spitze. Erst wenn man die derzeitige Spitze entfernt, weiß man, was die neue Spitze ist. vorher kann man nicht sagen, welches das "zweite" Element ist.

    das würde bedeuten, nach jedem pop() wird der gesamte Heap (also alle Elemente) erneut geprüft und miteinander verglichen?

    Nein! Wie kommst du darauf? Ich habe doch schon mit dem anderen Punkt erklärt, dass deine Vorstellungen wie man ein neues Element in eine vorsortierte Struktur einfügen kann, naiv waren. Ist es so schwer vorstellbar, dass deine Vorstellung, wie man einen vorsortierten Heap neu ordnet auch naiv ist?

    Du hast doch offensichtlich 'Heap' gegoogelt, sonst hättest du das Stichwort 'MaxHeap' nicht gekannt. Hast du nichts dazu gelesen und plapperst nur Stichworte nach?



  • @SeppJ sagte in priority queue verständnis:

    @WillyWilson sagte in priority queue verständnis:

    @SeppJ sagte in priority queue verständnis:

    Wie schon gesagt, ist eine priority queue nicht zwangsläufig sortiert. Sie braucht nicht einmal so etwas wie eine "Reihenfolge" zu haben. Der MaxHeap (siehe unten) hat keine Reihenfolge. Er hat nur eine Spitze. Erst wenn man die derzeitige Spitze entfernt, weiß man, was die neue Spitze ist. vorher kann man nicht sagen, welches das "zweite" Element ist.

    das würde bedeuten, nach jedem pop() wird der gesamte Heap (also alle Elemente) erneut geprüft und miteinander verglichen?

    Nein! Wie kommst du darauf? Ich habe doch schon mit dem anderen Punkt erklärt, dass deine Vorstellungen wie man ein neues Element in eine vorsortierte Struktur einfügen kann, naiv waren. Ist es so schwer vorstellbar, dass deine Vorstellung, wie man einen vorsortierten Heap neu ordnet auch naiv ist?

    Du hast doch offensichtlich 'Heap' gegoogelt, sonst hättest du das Stichwort 'MaxHeap' nicht gekannt. Hast du nichts dazu gelesen und plapperst nur Stichworte nach?

    dieser post ist weder konstruktiv noch hilfreich


  • Mod

    Er hatte auch nicht das Ziel, hilfreich für dich zu sein, sondern klar zu machen, dass ich nicht noch einmal erklären werde, was schon 3x gesagt wurde, aber offensichtlich nicht gelesen wurde. Dieses Ziel wurde erfolgreich erreicht.


Log in to reply