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:

1. Sein Wert ist nicht kleiner (oder nicht größer) als der Wert seines übergeordneten Knotens.
2. Seine linken und rechten Teilbäume sind ebenfalls ein Heap.

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. Heap-Klasse

(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 4, 1, 5, 9, 2, 6, 5, 3 };

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() eine Vergleichsfunktion dar, die den Typ des Heaps steuern kann.

(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();

2. priority_queue class

(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,Greater>q;

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

Um Elemente in der Prioritätswarteschlange zu löschen, können Sie direkt die Pop-Funktion verwenden, wie unten gezeigt:

q.pop();

2 Die Prioritätswarteschlange ist eine spezielle Warteschlange, die Elemente nach Priorität sortiert, wobei die Elemente mit der höchsten Priorität an den Anfang der Warteschlange und die Elemente mit der niedrigsten Priorität am Ende der Warteschlange gestellt werden. Sie können einen Heap verwenden, um eine Prioritätswarteschlange zu implementieren.

In C++ ist die Priority_queue-Klasse eine auf dem Heap basierende Prioritätswarteschlange. Sie kann die Funktionen in den oben genannten Heap- und Priority_queue-Klassen verwenden, um Elementeinfüge- und -löschvorgänge durchzuführen. Darüber hinaus wird die Top-Funktion auch in der Priority_queue-Klasse bereitgestellt, mit der auf das Element mit der höchsten Priorität zugegriffen wird, wie unten gezeigt:

priority_queue q;

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!