Cola de prioridad: la cola de prioridad es la extensión de la cola en la que los elementos asociados con la prioridad y los elementos que tienen mayor prioridad aparecen primero.
La cola de prioridad puede contener elementos con varios tipos de datos, como enteros, pares de enteros, tipos de datos personalizados. Pero una cosa es común que hay un elemento que define la prioridad del elemento.
Por lo tanto, la cola de prioridad de pares puede tener dos tipos de ordenación:
- Ordenado por el primer elemento del par
- Ordenado por el segundo elemento del par.
Cola de prioridad ordenada por primer elemento
En C++, si el elemento está en forma de pares, entonces, por defecto, la prioridad de los elementos depende del primer elemento. Por lo tanto, solo tenemos que usar la cola de prioridad de pares solamente.
C++
// C++ implementation of the // priority queue of pairs // ordered by the first element #include <iostream> #include <queue> using namespace std; // Function to print the data of // the priority queue ordered by first void showpq( priority_queue<pair<int, int> > g) { // Loop to print the elements // until the priority queue // is not empty while (!g.empty()) { cout << g.top().first << " " << g.top().second << endl; g.pop(); } cout << endl; } // Driver Code int main() { priority_queue<pair<int, int> > p1; // Insertion of elements p1.push(make_pair(4, 5)); p1.push(make_pair(5, 4)); p1.push(make_pair(1, 6)); p1.push(make_pair(7, 3)); p1.push(make_pair(9, 4)); showpq(p1); return 0; }
9 4 7 3 5 4 4 5 1 6
Nota: Si el primer elemento de algunos pares es el mismo, la comparación se realizará sobre la base del segundo elemento.
Cola de prioridad ordenada por segundo elemento (Max)
La idea es utilizar estructura con el concepto de sobrecarga del operador en la cola de prioridad para ordenar los pares por su segundo elemento.
A continuación se muestra la implementación de la cola de prioridad ordenada por segundo elemento:
C++
// C++ implementation of the // priority queue in which elements // are sorted by the second element #include <iostream> #include <queue> #include <vector> using namespace std; typedef pair<int, int> pd; // Structure of the condition // for sorting the pair by its // second elements struct myComp { constexpr bool operator()( pair<int, int> const& a, pair<int, int> const& b) const noexcept { return a.second < b.second; } }; // Function to show the elements // of the priority queue void showpq( priority_queue<pd, vector<pd>, myComp> g) { // Loop to print the elements // until the priority queue // is not empty while (!g.empty()) { cout << g.top().first << " " << g.top().second << endl; g.pop(); } cout << endl; } // Driver Code int main() { priority_queue<pd, vector<pd>, myComp> p1; p1.push(make_pair(4, 5)); p1.push(make_pair(5, 4)); p1.push(make_pair(1, 6)); p1.push(make_pair(7, 3)); p1.push(make_pair(9, 4)); // Function Call showpq(p1); return 0; }
1 6 4 5 9 4 5 4 7 3
Cola de prioridad ordenada por segundo elemento (Min)
La idea es utilizar la sobrecarga del operador para implementar la cola de prioridad ordenada por su segundo elemento con el elemento mínimo en la parte superior.
A continuación se muestra la implementación de la cola de prioridad:
C++
// C++ implementation of the priority // queue sorted by the second element // in the decreasing order #include <iostream> #include <queue> #include <vector> using namespace std; typedef pair<int, int> pd; // Structure of the operator // overloading for comparison struct myComp { constexpr bool operator()( pair<int, int> const& a, pair<int, int> const& b) const noexcept { return a.second > b.second; } }; // Function to print the elements // of the priority queue void showpq( priority_queue<pd, vector<pd>, myComp> g) { // Loop to print the elements // of the priority queue while (!g.empty()) { cout << g.top().first << " " << g.top().second << endl; g.pop(); } cout << endl; } // Driver Code int main() { priority_queue<pd, vector<pd>, myComp> p1; // Insertion of the elements p1.push(make_pair(4, 5)); p1.push(make_pair(5, 4)); p1.push(make_pair(1, 6)); p1.push(make_pair(7, 3)); p1.push(make_pair(9, 4)); showpq(p1); return 0; }
7 3 5 4 9 4 4 5 1 6
Publicación traducida automáticamente
Artículo escrito por shivamtripathi91 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA