C++-Containerklassen<priority_queue>

In C++,<priority_queue>Ist Teil der Standard Template Library (STL) und wird verwendet, um Prioritätswarteschlangen zu implementieren.

Eine Prioritätswarteschlange ist ein spezieller Warteschlangentyp, der es ermöglicht, schnell auf das Element mit der höchsten (oder niedrigsten) Priorität in der Warteschlange zuzugreifen.

In C++,priority_queueStandardmäßig ist sie ein Max-Heap, was bedeutet, dass das oberste Element der Warteschlange immer den größten Wert hat.

priority_queueIst ein Container-Adapter, der Heap-Operationen auf dem zugrunde liegenden Container bereitstellt. Er bietet keine Iteratoren und unterstützt keinen wahlfreien Zugriff.

Syntax

Die folgenden sindpriority_queueGrundlegende Syntax:

#include <queue>

// 声明一个整型优先队列
priority_queue<int> pq;

// 声明一个自定义类型的优先队列，需要提供比较函数
struct compare {
    bool operator()(int a, int b) {
        return a > b; // 这里定义了最小堆
    }
};
priority_queue<int, vector<int>, compare> pq_min;

Häufige Operationen

  • empty(): Prüfen, ob die Warteschlange leer ist.
  • size(): Gibt die Anzahl der Elemente in der Warteschlange zurück.
  • top(): Gibt das Element an der Spitze der Warteschlange zurück (ohne es zu entfernen).
  • push(): Fügt ein Element zur Warteschlange hinzu.
  • pop(): Entfernt das Element an der Spitze der Warteschlange.

Beispiel

Nachfolgend ein Beispiel unter Verwendung vonpriority_queueEin einfaches Beispiel dafür: Wir erstellen einen Max-Heap und zeigen, wie man Elemente hinzufügt und das Element an der Spitze der Warteschlange abruft.

Beispiel

#include <iostream>
#include <queue>

int main() {
    // Eine Integer-Prioritätswarteschlange erstellen
    std::priority_queue<int> pq;

    // Elemente zur Prioritätswarteschlange hinzufügen
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    // Elemente in der Warteschlange ausgeben
    std::cout << "Elemente in der Warteschlange:" << std::endl;
    while (!pq.empty()) {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }

    return 0;
}

Ausgabeergebnis:

队列中的元素：
50
30
20
10

Benutzerdefinierte Priorität

Wenn Sie einen Min-Heap benötigen, können Sie ihn durch Anpassen der Vergleichsfunktion implementieren:

Beispiel

#include <iostream>
#include <queue>
#include <vector>

struct compare {
    bool operator()(int a, int b) {
        return a > b; // Definiere einen Min-Heap
    }
};

int main() {
    // Prioritätswarteschlange für einen benutzerdefinierten Typ mithilfe eines Min-Heaps erstellen
    std::priority_queue<int, std::vector<int>, compare> pq_min;

    // Elemente zur Prioritätswarteschlange hinzufügen
    pq_min.push(30);
    pq_min.push(10);
    pq_min.push(50);
    pq_min.push(20);

    // Elemente in der Warteschlange ausgeben
    std::cout << "Elemente im Min-Heap:" << std::endl;
    while (!pq_min.empty()) {
        std::cout << pq_min.top() << std::endl;
        pq_min.pop();
    }

    return 0;
}

Ausgabeergebnis:

最小堆中的元素：
10
20
30
50

<priority_queue>Es ist ein sehr nützlicher Container in der C++ STL, besonders geeignet für Szenarien, in denen schneller Zugriff auf das Element mit der höchsten oder niedrigsten Priorität benötigt wird. Durch Anpassen der Vergleichsfunktion können wir auf einfache Weise einen Max-Heap oder einen Min-Heap implementieren. Ich hoffe, dieser Artikel kann Anfängern helfen, ihn besser zu verstehen und zu verwenden.priority_queue。

Weitere Erweiterungen