Heim > Artikel > Backend-Entwicklung > Heap und Prioritätswarteschlange in C++
Heap und Prioritätswarteschlange sind häufig verwendete Datenstrukturen in C++, und beide haben einen wichtigen Anwendungswert. In diesem Artikel werden der Heap und die Prioritätswarteschlange vorgestellt und analysiert, um den Lesern zu helfen, sie besser zu verstehen und zu verwenden.
1. Heap
Der Heap ist eine spezielle Baumdatenstruktur, die zur Implementierung von Prioritätswarteschlangen verwendet werden kann. Im Heap erfüllt jeder Knoten die folgenden Eigenschaften:
Wir bezeichnen einen Heap, der nicht kleiner als sein übergeordneter Knoten ist, als „Min-Heap“ und einen Heap, der nicht größer als sein übergeordneter Knoten ist, als „Max-Heap“. Darüber hinaus ist der Heap normalerweise ein vollständiger Binärbaum, dh die Knoten auf anderen Ebenen sind voll, mit Ausnahme der letzten Ebene, auf der die Knoten von links nach rechts angeordnet sind.
In C++ stellt die STL-Bibliothek zwei Klassen bereit, Heap und Priority_queue, um den Heap zu implementieren. Unter diesen stellt die Heap-Klasse Heap-Operationsfunktionen wie make_heap, push_heap, pop_heap usw. bereit, und die Priority_queue-Klasse ist eine Prioritätswarteschlange, die auf der Heap-Implementierung basiert. Schauen wir uns als Nächstes die Verwendung von Heap und Priority_queue an.
(1) Erstellen Sie einen Heap
Bevor Sie einen Heap erstellen, müssen Sie ein Vektortyp-Array erstellen, um die zu sortierenden Zahlen zu speichern:
vector
Dann können wir die Funktion make_heap verwenden, um das Vektortyp-Array in einen Heap zu konvertieren:
make_heap(v.begin(), v.end (), great< ;int>());
Unter diesen stellt great
(2) Elemente einfügen
Um Elemente in den Heap einzufügen, können Sie die Funktion push_heap wie folgt verwenden:
v.push_back(7);
push_heap(v.begin(), v.end (), größer());
(3) Elemente löschen
Um Elemente aus dem Heap zu löschen, können Sie die Funktion pop_heap verwenden, die das oberste Element des Heaps an die letzte Position des Heaps verschiebt und löschen Sie das Element aus dem Heap. Die Verwendung dieser Funktion ist wie folgt:
pop_heap(v.begin(), v.end(), great
v.pop_back();
(1 ) Erstellen Sie einen Heap
Im Gegensatz zur Heap-Klasse kann die Priority_queue-Klasse den Heap-Typ beim Deklarieren des Objekts wie folgt angeben:
priority_queue
This bedeutet, einen minimalen Heap zu erstellen.
(2) Elemente einfügen
Das Einfügen von Elementen in die Prioritätswarteschlange kann direkt die Push-Funktion verwenden, wie unten gezeigt:
q.push(4);q.push(1); q.push(9);
(3) Elemente löschen
q.push(2);
q.push (4);q .push(1);
q.push(9);cout
Dieser Artikel stellt vor den Heap und die Priorität in der C++-Warteschlange und analysierte die Verwendungs- und Implementierungsprinzipien von Heap bzw. Prioritätswarteschlange. Durch das Studium dieses Artikels können Leser diese beiden Datenstrukturen besser verstehen und sie flexibel in der tatsächlichen Programmierung verwenden. Gleichzeitig sollten Leser auf den Zeitpunkt und die Vorsichtsmaßnahmen für die Verwendung des Heaps und der Prioritätswarteschlange achten, um die Korrektheit und Effizienz des Codes sicherzustellen.
Das obige ist der detaillierte Inhalt vonHeap und Prioritätswarteschlange in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!