Classes de conteneurs C++<priority_queue>

En C++,<priority_queue>Fait partie de la Standard Template Library (STL) et est utilisé pour implémenter des files de priorité.

Une file de priorité est un type spécial de file qui permet d'accéder rapidement à l'élément ayant la priorité la plus élevée (ou la plus faible) dans la file.

En C++,priority_queuePar défaut, il s'agit d'un max-heap, ce qui signifie que l'élément au sommet de la file a toujours la valeur la plus grande.

priority_queueEst un adaptateur de conteneur qui fournit des opérations de tas sur le conteneur sous-jacent. Il ne fournit pas d'itérateurs et ne prend pas en charge l'accès aléatoire.

Syntaxe

Les suivantes sontpriority_queueSyntaxe de base :

#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;

Opérations courantes

  • empty(): Vérifier si la file est vide.
  • size(): Retourner le nombre d'éléments dans la file.
  • top(): Retourner l'élément au sommet de la file (sans le supprimer).
  • push(): Ajouter un élément à la file.
  • pop(): Supprimer l'élément au sommet de la file.

Exemple

Voici un exemple utilisantpriority_queueUn exemple simple : nous allons créer un max-heap et montrer comment ajouter des éléments et récupérer l'élément au sommet de la file.

Exemple

#include <iostream>
#include <queue>

int main() {
    // Créer une file de priorité d'entiers
    std::priority_queue<int> pq;

    // Ajouter des éléments à la file de priorité
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    // Afficher les éléments de la file
    std::cout << "Éléments dans la file :" << std::endl;
    while (!pq.empty()) {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }

    return 0;
}

Résultat de sortie :

队列中的元素:
50
30
20
10

Priorité personnalisée

Si vous avez besoin d'un tas-min, vous pouvez l'implémenter en personnalisant la fonction de comparaison :

Exemple

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

struct compare {
    bool operator()(int a, int b) {
        return a > b; // Définir un tas min
    }
};

int main() {
    // Créer une file de priorité de type personnalisé à l'aide d'un tas min
    std::priority_queue<int, std::vector<int>, compare> pq_min;

    // Ajouter des éléments à la file de priorité
    pq_min.push(30);
    pq_min.push(10);
    pq_min.push(50);
    pq_min.push(20);

    // Afficher les éléments de la file
    std::cout << "Éléments dans le tas min :" << std::endl;
    while (!pq_min.empty()) {
        std::cout << pq_min.top() << std::endl;
        pq_min.pop();
    }

    return 0;
}

Résultat de sortie :

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

<priority_queue>C'est un conteneur très utile dans la STL C++, particulièrement adapté aux scénarios où un accès rapide à l'élément de priorité la plus élevée ou la plus faible est nécessaire. En personnalisant la fonction de comparaison, nous pouvons facilement implémenter un tas max ou un tas min. J'espère que cet article aidera les débutants à mieux le comprendre et à mieux l'utiliser.priority_queue。

autres extensions