cola de prioridad
Las colas de prioridad son un tipo de adaptadores de contenedores, diseñados específicamente de modo que el primer elemento de la cola es el mayor de todos los elementos de la cola y los elementos están en orden no creciente (por lo tanto, podemos ver que cada elemento de la cola tiene una prioridad {orden fijo}). Generalmente, las colas de prioridad son de dos tipos: montón máximo y montón mínimo, pero siempre podemos pasar un comparador a una cola de prioridad.
Funciones utilizadas con Priority Queue:
- vacío(): esta función devuelve si la cola está vacía.
- size(): Esta función devuelve el tamaño de la cola.
- top(): Devuelve una referencia al elemento superior de la cola.
- push(x): Esta función agrega el elemento ‘x’ al final de la cola.
Mapa
Los mapas son contenedores asociativos que almacenan elementos en forma de mapa. Cada elemento tiene un valor clave y un valor asignado. Dos valores asignados no pueden tener los mismos valores clave. Internamente se implementa como BST autoequilibrado.
Funciones utilizadas con Mapa:
- begin(): Devuelve un iterador al primer elemento del mapa
- end(): Devuelve un iterador al elemento teórico que sigue al último elemento en el mapa
- size(): Devuelve el número de elementos en el mapa
- vacío(): devuelve si el mapa está vacío
Este artículo se centra en cómo se puede usar la cola de prioridad de mapas en C++. La cola de prioridad de mapas puede ser bastante útil al diseñar estructuras de datos complejas.
Cola de mapas de prioridad máxima de montón:
- Cola de prioridad de pila máxima en la que los mapas se organizan en orden no descendente:
cola_prioridad<mapa<tipo_datos1, tipo_datos2>> cola_prioridad;
Aquí,
data_type1: es el tipo de datos para la clave.
data_type2: es el tipo de datos para el valor.
- Cola de prioridad de pila máxima en la que los mapas se organizan en orden no ascendente:
cola_prioridad<mapa<tipo_datos1, tipo_datos2, mayor<tipo_datos1>>> cola_prioridad;
Aquí,
data_type1: es el tipo de datos para la clave.
data_type2: es el tipo de datos para el valor.
Cola de prioridad de montón mínimo de mapas:
- Cola de prioridad de montón mínimo en la que los mapas se organizan en orden no descendente:
cola_prioridad<mapa<tipo_datos1, tipo_datos2>, vector<mapa<tipo_datos1, tipo_datos2>>,
mayor<mapa<tipo_datos1, tipo_datos2>>> cola_prioridad;Aquí,
data_type1: es el tipo de datos para la clave.
data_type2: es el tipo de datos para el valor.
- Cola de prioridad de montón mínimo en la que los mapas se organizan en orden no ascendente:
cola_prioridad<mapa<tipo_datos1, tipo_datos2>, vector<mapa<tipo_datos1, tipo_datos2, mayor<tipo_datos1>>>,
mayor<mapa<tipo_datos1, tipo_datos2, mayor<tipo_datos1>>>> cola_prioridad;Aquí,
data_type1: es el tipo de datos para la clave.
data_type2: es el tipo de datos para el valor.
Cola de prioridad personalizada de mapas (usando comparador):
cola_prioridad<mapa<tipo_datos1, tipo_datos2>, vector<mapa<tipo_datos1, tipo_datos2>>,
myComparator> cola_prioridad;Aquí,
data_type1: es el tipo de datos para la clave.
data_type2: es el tipo de datos para el valor.
myComparator: es la clase o estructura del comparador.
A continuación se muestra el fragmento de código C++ para el comparador:
C++
// Comparator structure
struct myComparator
{
int operator()(const map<data_type1,
data_type2>& map1,
const map<data_type1,
data_type2>& map2)
{
// body
}
};
// Comparator class
struct myComparator
{
public:
int operator()(const map<data_type1,
data_type2>& map1,
const map<data_type1,
data_type2>& map2)
{
// body
}
};
Cola de mapas de prioridad máxima de almacenamiento dinámico
Por defecto, la cola de prioridad es max-heap. Entonces, en el caso de un par de mapas en la cola de prioridad máxima del montón, la clave y el valor de los dos elementos del mapa se comparan simultáneamente, uno por uno. Si la clave del primer elemento de los dos mapas es igual, se compara el valor del primer elemento, y si el valor del primer elemento de ambos mapas también es igual, se compara la clave del segundo elemento. Si la clave del segundo elemento de los dos mapas también es igual, luego se compara el valor del segundo elemento y así sucesivamente. El mapa que tiene la clave o valor más grande durante la comparación se convierte en el elemento superior de la cola de prioridad.
A continuación se muestran los programas de C++ para demostrar el funcionamiento de la cola de mapas de prioridad máxima del montón, de modo que los elementos de los mapas se ordenan en orden no descendente por clave:
Ejemplo 1:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority queue contents
void print(priority_queue<map<int, int> >
priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, int> map1 = priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, int> >
priorityQueue;
// Declaring a map whose key is
// integer type and, value is also
// integer type
map<int, int> map1;
map1[1] = 11;
map1[2] = 22;
map1[3] = 33;
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map2;
map2[1] = 11;
map2[2] = 22;
map2[3] = 44;
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map3;
map3[1] = 11;
map3[2] = 22;
map3[4] = 33;
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map4;
map4[11] = 11;
map4[2] = 22;
map4[4] = 33;
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:2 , valor:22 clave:4 , valor:33 clave:11 , valor:11 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:4 , valor:33 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:3 , valor:44 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:3 , valor:33 ]
Ejemplo 2:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority
// queue contents
void print(priority_queue<map<int, string> >
priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, string> map1 =
priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, string> >
priorityQueue;
// Declaring a map whose key is
// integer type and, value is
// also integer type
map<int, string> map1;
map1[1] = "geeks";
map1[2] = "for";
map1[3] = "geeks";
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map2;
map2[1] = "geeks";
map2[2] = "for";
map2[3] = "learning";
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map3;
map3[1] = "geeks";
map3[2] = "for";
map3[4] = "geeks";
priorityQueue.push(map3);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:1 , valor:geeks clave:2 , valor:for clave:4 , valor:geeks ]
[ clave:1 , valor:geeks clave:2 , valor:for clave:3 , valor:aprendizaje ]
[ clave:1 , valor:geeks clave:2 , valor:para clave:3 , valor:geeks ]
Cola máxima de mapas con prioridad de almacenamiento dinámico
A continuación se muestran los programas de C++ para demostrar el funcionamiento de la cola de mapas de prioridad máxima del montón, de modo que los elementos de los mapas se ordenan en orden no ascendente por clave:
Ejemplo 1:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority queue contents
void print(priority_queue<map<int, int,
greater<int> > >
priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, int, greater<int> > map1 =
priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, int,
greater<int> > >
priorityQueue;
// Declaring a map whose key is
// integer type and, value is also
// integer type
map<int, int, greater<int> > map1;
map1[1] = 11;
map1[2] = 22;
map1[3] = 33;
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int, greater<int> > map2;
map2[1] = 11;
map2[2] = 22;
map2[3] = 44;
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int, greater<int> > map3;
map3[1] = 11;
map3[2] = 22;
map3[4] = 33;
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int, greater<int> > map4;
map4[1] = 11;
map4[2] = 22;
map4[4] = 33;
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:4 , valor:33 clave:2 , valor:22 clave:1 , valor:11 ]
[ clave:4 , valor:33 clave:2 , valor:22 clave:1 , valor:11 ]
[ clave:3 , valor:44 clave:2 , valor:22 clave:1 , valor:11 ]
[ clave:3 , valor:33 clave:2 , valor:22 clave:1 , valor:11 ]
Ejemplo 2:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority queue contents
void print(priority_queue<map<int, string,
greater<int> > >
priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, string, greater<int> > map1 =
priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, string,
greater<int> > >
priorityQueue;
// Declaring a map whose key is
// integer type and, value is also
// integer type
map<int, string, greater<int> > map1;
map1[1] = "geeks";
map1[2] = "for";
map1[3] = "geeks";
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string, greater<int> > map2;
map2[1] = "geeks";
map2[2] = "for";
map2[3] = "learning";
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string, greater<int> > map3;
map3[1] = "geeks";
map3[2] = "for";
map3[4] = "geeks";
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string, greater<int> > map4;
map4[1] = "Code";
map4[2] = "For";
map4[4] = "Fun";
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:4 , valor:geeks clave:2 , valor:para clave:1 , valor:geeks ]
[ clave:4 , valor:Fun clave:2 , valor:Para clave:1 , valor:Código ]
[ clave:3 , valor:aprendizaje clave:2 , valor:for clave:1 , valor:geeks ]
[ clave:3 , valor:geeks clave:2 , valor:for clave:1 , valor:geeks ]
Cola de prioridad de montón mínimo de mapas
En el caso de un par de mapas en la cola de prioridad min-heap , la clave y el valor de los dos elementos del mapa se comparan simultáneamente, uno por uno. Si la clave del primer elemento de los dos mapas es igual, se compara el valor del primer elemento, y si el valor del primer elemento de ambos mapas también es igual, se compara la clave del segundo elemento. Si la clave del segundo elemento de los dos mapas también es igual, luego se compara el valor del segundo elemento y así sucesivamente. El mapa que tiene la clave o el valor más pequeño durante la comparación se convierte en el elemento superior de la cola de prioridad.
A continuación se muestran los programas de C++ para demostrar el funcionamiento de la cola de mapas de prioridad min-heap, de modo que los elementos del mapa se organizan en orden no descendente por clave:
Ejemplo 1:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority queue contents
void print(priority_queue<map<int, int>,
vector<map<int, int> >,
greater<map<int, int> > >
priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, int> map1 = priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, int>,
vector<map<int, int> >,
greater<map<int, int> > >
priorityQueue;
// Declaring a map whose key is
// integer type and, value is
// also integer type
map<int, int> map1;
map1[1] = 11;
map1[2] = 22;
map1[3] = 33;
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map2;
map2[1] = 11;
map2[2] = 22;
map2[3] = 44;
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map3;
map3[1] = 11;
map3[2] = 22;
map3[4] = 33;
priorityQueue.push(map3);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:1 , valor:11 clave:2 , valor:22 clave:3 , valor:33 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:3 , valor:44 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:4 , valor:33 ]
Ejemplo 2:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority queue contents
void print(priority_queue<map<int, string>,
vector<map<int, string> >,
greater<map<int, string> > >
priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, string> map1 =
priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, string>,
vector<map<int, string> >,
greater<map<int, string> > >
priorityQueue;
// Declaring a map whose key is
// integer type and, value is also
// integer type
map<int, string> map1;
map1[1] = "geeks";
map1[2] = "for";
map1[3] = "geeks";
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map2;
map2[1] = "geeks";
map2[2] = "for";
map2[3] = "learning";
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map3;
map3[1] = "geeks";
map3[2] = "for";
map3[4] = "geeks";
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map4;
map4[1] = "Code";
map4[2] = "For";
map4[4] = "Fun";
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:1 , valor:Código clave:2 , valor:Para clave:4 , valor:Divertido ]
[ clave:1 , valor:geeks clave:2 , valor:para clave:3 , valor:geeks ]
[ clave:1 , value:geeks key:2 , value:for key:3 , value:learning ]
[ key:1 , value:geeks key:2 , value:for key:4 , value:geeks ]
Cola de prioridad mínima de almacenamiento dinámico de mapas
A continuación se muestran los programas de C++ para demostrar el funcionamiento de la cola de mapas de prioridad min-heap, de modo que los elementos del mapa se organizan en orden no ascendente por la clave:
Ejemplo 1:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority
// queue contents
void print(priority_queue<map<int, int>,
vector<map<int, int,
greater<int> > >,
greater<map<int, int,
greater<int> > > >
priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, int, greater<int> > map1 =
priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, int>,
vector<map<int, int,
greater<int> > >,
greater<map<int, int,
greater<int> > > >
priorityQueue;
// Declaring a map whose key is
// integer type and, value is also
// integer type
map<int, int, greater<int> > map1;
map1[1] = 11;
map1[2] = 22;
map1[3] = 33;
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int, greater<int> > map2;
map2[1] = 11;
map2[2] = 22;
map2[3] = 44;
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int, greater<int> > map3;
map3[1] = 11;
map3[2] = 22;
map3[4] = 33;
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int, greater<int> > map4;
map4[1] = 11;
map4[2] = 22;
map4[4] = 33;
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:3 , valor:33 clave:2 , valor:22 clave:1 , valor:11 ]
[ clave:3 , valor:44 clave:2 , valor:22 clave:1 , valor:11 ]
[ clave:4 , valor:33 clave:2 , valor:22 clave:1 , valor:11 ]
[ clave:4 , valor:33 clave:2 , valor:22 clave:1 , valor:11 ]
Ejemplo 2:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority
// queue contents
void print(priority_queue<
map<int, string,
greater<int> >,
vector<map<int, string,
greater<int> > >,
greater<map<int, string,
greater<int> > > >
priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, string, greater<int> > map1 =
priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, string,
greater<int> >,
vector<map<int, string,
greater<int> > >,
greater<map<int, string,
greater<int> > > >
priorityQueue;
// Declaring a map whose key is
// integer type and, value is
// also integer type
map<int, string, greater<int> > map1;
map1[1] = "geeks";
map1[2] = "for";
map1[3] = "geeks";
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string, greater<int> > map2;
map2[1] = "geeks";
map2[2] = "for";
map2[3] = "learning";
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string, greater<int> > map3;
map3[1] = "geeks";
map3[2] = "for";
map3[4] = "geeks";
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string, greater<int> > map4;
map4[1] = "Code";
map4[2] = "For";
map4[4] = "Fun";
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:3 , valor:geeks clave:2 , valor:para clave:1 , valor:geeks ]
[ clave:3 , valor:aprendizaje clave:2 , valor:para clave:1 , valor:geeks ]
[ clave:4 , valor:Fun key:2 , value:For key:1 , value:Code ]
[ key:4 , value:geeks key:2 , value:for key:1 , value:geeks ]
Cola de prioridad personalizada de mapas
A continuación se muestran los programas C++ para demostrar el funcionamiento de la cola de prioridad personalizada de mapas:
Ejemplo 1:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
struct myComparator
{
int operator()(const map<int, int>& map1,
const map<int, int>& map2)
{
// Max-heap priority queue
for (auto it1 = map1.begin(),
it2 = map2.begin();
it1 != map1.end(),
it2 != map2.end();
it1++, it2++)
{
auto key1 = it1->first;
auto value1 = it1->second;
auto key2 = it2->first;
auto value2 = it2->second;
if (key1 == key2)
{
if (value1 == value2)
continue;
return value1 < value2;
}
return key1 < key2;
}
return map1.size() <= map2.size();
}
};
// Function to print priority
// queue contents
void print(priority_queue<map<int, int>,
vector<map<int, int> >,
myComparator> priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, int> map1 =
priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, int>,
vector<map<int, int> >,
myComparator>
priorityQueue;
// Declaring a map whose key is
// integer type and, value is
// also integer type
map<int, int> map1;
map1[1] = 11;
map1[2] = 22;
map1[3] = 33;
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map2;
map2[1] = 11;
map2[2] = 22;
map2[3] = 44;
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map3;
map3[1] = 11;
map3[2] = 22;
map3[4] = 33;
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map4;
map4[1] = 11;
map4[2] = 22;
map4[4] = 33;
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:1 , valor:11 clave:2 , valor:22 clave:4 , valor:33 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:4 , valor:33 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:3 , valor:44 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:3 , valor:33 ]
Ejemplo 2:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
struct myComparator
{
int operator()(const map<int, int>& map1,
const map<int, int>& map2)
{
// Min-heap priority queue
for (auto it1 = map1.begin(),
it2 = map2.begin();
it1 != map1.end(),
it2 != map2.end();
it1++, it2++)
{
auto key1 = it1->first;
auto value1 = it1->second;
auto key2 = it2->first;
auto value2 = it2->second;
if (key1 == key2)
{
if (value1 == value2)
continue;
return value1 > value2;
}
return key1 > key2;
}
return map1.size() >= map2.size();
}
};
// Function to print priority
// queue contents
void print(priority_queue<map<int, int>,
vector<map<int, int> >,
myComparator> priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, int> map1 =
priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, int>,
vector<map<int, int> >,
myComparator> priorityQueue;
// Declaring a map whose key is
// integer type and, value is also
// integer type
map<int, int> map1;
map1[1] = 11;
map1[2] = 22;
map1[3] = 33;
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map2;
map2[1] = 11;
map2[2] = 22;
map2[3] = 44;
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map3;
map3[1] = 11;
map3[2] = 22;
map3[4] = 33;
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, int> map4;
map4[1] = 11;
map4[2] = 22;
map4[4] = 33;
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave:1 , valor:11 clave:2 , valor:22 clave:3 , valor:33 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:3 , valor:44 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:4 , valor:33 ]
[ clave:1 , valor:11 clave:2 , valor:22 clave:4 , valor:33 ]
Ejemplo 3:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
struct myComparator
{
int operator()(const map<int, string>& map1,
const map<int, string>& map2)
{
// Max-heap priority queue
for (auto it1 = map1.begin(),
it2 = map2.begin();
it1 != map1.end(),
it2 != map2.end();
it1++, it2++)
{
auto key1 = it1->first;
auto value1 = it1->second;
auto key2 = it2->first;
auto value2 = it2->second;
if (key1 == key2)
{
if (value1 == value2)
continue;
return value1 < value2;
}
return key1 < key2;
}
return map1.size() <= map2.size();
}
};
// Function to print priority
// queue contents
void print(priority_queue<map<int, string>,
vector<map<int, string> >,
myComparator> priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, string> map1 =
priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , " <<
"value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, string>,
vector<map<int, string> >,
myComparator> priorityQueue;
// Declaring a map whose key is
// integer type and, value is
// also integer type
map<int, string> map1;
map1[1] = "apple";
map1[2] = "boy";
map1[3] = "cat";
priorityQueue.push(map1);
// Declaring another map whose key
// is integer type and, value is
// also integer type
map<int, string> map2;
map2[1] = "apple";
map2[2] = "bat";
map2[4] = "eat";
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map3;
map3[1] = "apple";
map3[2] = "ao";
map3[10] = "fo";
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map4;
map4[1] = "code";
map4[2] = "for";
map4[10] = "fun";
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave: 1 , valor: código clave: 2 , valor: para clave: 10 , valor: divertido ]
[ clave: 1 , valor: manzana clave: 2 , valor: niño clave: 3 , valor: gato ]
[ clave: 1 , valor:clave de manzana:2 , valor:clave de murciélago:4 , valor:comer ]
[ clave:1 , valor:clave de manzana:2 , valor:ao clave:10 , valor:fo ]
Ejemplo 4:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
struct myComparator
{
int operator()(const map<int, string>& map1,
const map<int, string>& map2)
{
// Min-heap priority queue
for (auto it1 = map1.begin(),
it2 = map2.begin();
it1 != map1.end(),
it2 != map2.end();
it1++, it2++)
{
auto key1 = it1->first;
auto value1 = it1->second;
auto key2 = it2->first;
auto value2 = it2->second;
if (key1 == key2)
{
if (value1 == value2)
continue;
return value1 > value2;
}
return key1 > key2;
}
return map1.size() >= map2.size();
}
};
// Function to print priority
// queue contents
void print(priority_queue<map<int, string>,
vector<map<int, string> >,
myComparator> priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a map itself
map<int, string> map1 = priorityQueue.top();
cout << "[ ";
// Print the map elements
for (auto pair1 : map1)
{
// Each element in a map is a key,
// value pair
cout << "key:" << pair1.first << " , "
<< "value:" << pair1.second << " ";
}
cout << ']';
cout << '\n';
// Pop out the topmost map
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Priority queue of map
// Each element of the priority
// queue is a map
priority_queue<map<int, string>,
vector<map<int, string> >,
myComparator> priorityQueue;
// Declaring a map whose key is
// integer type and, value is
// also integer type
map<int, string> map1;
map1[1] = "apple";
map1[2] = "boy";
map1[3] = "cat";
priorityQueue.push(map1);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map2;
map2[1] = "apple";
map2[2] = "bat";
map2[4] = "eat";
priorityQueue.push(map2);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map3;
map3[1] = "apple";
map3[2] = "ao";
map3[10] = "fo";
priorityQueue.push(map3);
// Declaring another map whose key is
// integer type and, value is also
// integer type
map<int, string> map4;
map4[1] = "code";
map4[2] = "for";
map4[10] = "fun";
priorityQueue.push(map4);
// Calling print function
print(priorityQueue);
return 0;
}
Producción:
[ clave: 1 , valor: clave de manzana: 2 , valor: clave ao: 10 , valor: fo ]
[ clave: 1 , valor: clave de manzana: 2 , valor: clave de murciélago: 4 , valor: comer ]
[ clave: 1 , valor:manzana clave:2 , valor:niño clave:3 , valor:gato ]
[ clave:1 , valor:código clave:2 , valor:for clave:10 , valor:diversión ]