A Cola de prioridad de C++ es un tipo de adaptador de contenedor, diseñado específicamente de modo que el primer elemento de la cola sea el mayor o el más pequeño de todos los elementos de la cola, y los elementos estén en orden no creciente ni decreciente (por lo tanto, podemos ver que cada elemento de la cola tiene una prioridad {orden fijo}).
En C++ STL, el elemento superior siempre es el mayor de forma predeterminada. También podemos cambiarlo al elemento más pequeño en la parte superior. Las colas de prioridad se crean en la parte superior del montón máximo y utilizan una matriz o un vector como estructura interna. En lenguaje sencillo, Cola de prioridad STL es la implementación de C++
// C++ program to demonstrate the use of priority_queue> #include> #include> using> namespace> std;> // driver code> int> main()> {> >int> arr[6] = { 10, 2, 4, 8, 6, 9 };> >// defining priority queue> >priority_queue<>int>>pq;> >// printing array> >cout <<>'Array: '>;> >for> (>auto> i : arr) {> >cout << i <<>' '>;> >}> >cout << endl;> >// pushing array sequentially one by one> >for> (>int> i = 0; i <6; i++) {> >pq.push(arr[i]);> >}> >// printing priority queue> >cout <<>'Priority Queue: '>;> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >return> 0;> }> |
>
>Producción
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Cola de prioridad máxima del montón (esquema predeterminado)
¿Cómo crear un montón mínimo para la cola de prioridad?
Como vimos anteriormente, una cola de prioridad se implementa como montón máximo de forma predeterminada en C++, pero también nos brinda una opción para cambiarla a montón mínimo pasando otro parámetro mientras creamos una cola de prioridad.
Sintaxis:
priority_queue gq;>
dónde,
- 'int' es el tipo de elementos que desea almacenar en la cola de prioridad. En este caso, es un número entero. puedes reemplazar En t con cualquier otro tipo de datos que necesite. 'vector' es el tipo de contenedor interno que se utiliza para almacenar estos elementos. std::priority_queue no es un contenedor en sí mismo sino un adoptante de contenedor. Envuelve otros contenedores. En este ejemplo, estamos usando un vector , pero puedes elegir un contenedor diferente que admita los métodos front(), push_back() y pop_back().
- ‘ mayor que 'es una función de comparación personalizada. Esto determina cómo se ordenan los elementos dentro de la cola de prioridad. En este ejemplo específico, mayor configura un montón mínimo . Significa que el elemento más pequeño estará en la parte superior de la cola.
En el caso del montón máximo, no tuvimos que especificarlos ya que los valores predeterminados ya son adecuados para el montón máximo.
Ejemplo:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, mayor que<>int>>>g)> {> >while> (!g.empty()) {> >cout <<>' '> << g.top();> >g.pop();> >}> >cout <<>'
'>;> }> void> showArray(>int>* arr,>int> n)> {> >for> (>int> i = 0; i cout << arr[i] << ' '; } cout << endl; } // Driver Code int main() { int arr[6] = { 10, 2, 4, 8, 6, 9 }; priority_queue |
>
>Producción
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Cola de prioridad mínima del montón
Nota: La sintaxis anterior puede ser difícil de recordar, por lo que en el caso de valores numéricos, podemos multiplicar los valores por -1 y usar el montón máximo para obtener el efecto del montón mínimo. No solo eso, podemos usar un método de clasificación personalizado reemplazando mayor que con función de comparador personalizado.
Métodos de cola prioritaria
La siguiente lista de todos los métodos de la clase std::priority_queue:
| Método | Definición |
|---|---|
| cola_prioridad::vacía() | Devuelve si la cola está vacía. |
| cola_prioridad::tamaño() | Devuelve el tamaño de la cola. |
| cola_prioridad::arriba() | Devuelve una referencia al elemento superior de la cola. |
| cola_prioridad::push() | Agrega el elemento 'g' al final de la cola. |
| cola_prioridad::pop() | Elimina el primer elemento de la cola. |
| cola_prioridad::intercambio() | Se utiliza para intercambiar el contenido de dos colas siempre que las colas deban ser del mismo tipo, aunque los tamaños pueden diferir. |
| prioridad_queue::emplazar() | Se utiliza para insertar un nuevo elemento en el contenedor de la cola de prioridad. |
| cola_prioridad tipo_valor | Representa el tipo de objeto almacenado como elemento en una cola_prioritaria. Actúa como sinónimo del parámetro de plantilla. |
Operaciones en cola de prioridad en C++
1. Insertar y eliminar elementos de una cola prioritaria
El empujar() El método se utiliza para insertar un elemento en la cola de prioridad. Para eliminar un elemento de la cola de prioridad, estallido() Se utiliza el método porque elimina el elemento con mayor prioridad.
A continuación se muestra el programa C++ para varias funciones en la cola de prioridad:
C++
// C++ Program to demonstrate various> // method/function in Priority Queue> #include> #include> using> namespace> std;> // Implementation of priority queue> void> showpq(priority_queue<>int>>gq)> {> >priority_queue<>int>>g = gq;> >while> (!g.empty()) {> >cout <<>' '> << g.top();> >g.pop();> >}> >cout <<>'
'>;> }> // Driver Code> int> main()> {> >priority_queue<>int>>gquiz;> >// used in inserting the element> >gquiz.push(10);> >gquiz.push(30);> >gquiz.push(20);> >gquiz.push(5);> >gquiz.push(1);> >cout <<>'The priority queue gquiz is : '>;> > >// used for highlighting the element> >showpq(gquiz);> >// used for identifying the size> >// of the priority queue> >cout <<>'
gquiz.size() : '> <<> >gquiz.size();> >// used for telling the top element> >// in priority queue> >cout <<>'
gquiz.top() : '> <<> >gquiz.top();> >// used for popping the element> >// from a priority queue> >cout <<>'
gquiz.pop() : '>;> >gquiz.pop();> >showpq(gquiz);> >return> 0;> }> |
>
>Producción
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Consulte el final para el análisis de complejidad.
Nota : Arriba se muestra uno de los métodos de inicialización de la cola prioritaria. Para saber más sobre la inicialización eficiente de la cola de prioridad, haga clic aquí.
2. Para acceder al elemento superior de la cola de prioridad
Se puede acceder al elemento superior de la cola de prioridad utilizando el arriba() método.
C++
// C++ program to access the top> // element of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >// create a priority queue of int> >priority_queue<>int>>números;> >// add items to priority_queue> >numbers.push(1);> >numbers.push(20);> >numbers.push(7);> >// get the element at the top> >cout <<>'Top element: '> <<> >numbers.top();> >return> 0;> }> |
>
>Producción
Top element: 20>
Consulte el final para el análisis de complejidad.
Nota: Solo podemos acceder al elemento superior en la cola de prioridad.
3. Para comprobar si la cola de prioridad está vacía o no:
Usamos el método vacío () para verificar si la cola_prioridad está vacía. Este método devuelve:
- True – Se devuelve cuando la cola de prioridad está vacía y se representa con 1 False – Se produce cuando la cola de prioridad no está vacía o False y se caracteriza por 0
Ejemplo:
C++
// C++ program to demonstrate> // Implementation of empty() function> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >priority_queue<>int>>pqueueGFG;> >pqueueGFG.push(1);> > >// Priority Queue becomes 1> >// check if it is empty or not> >if> (pqueueGFG.empty())> >{> >cout <<>'Empty or true'>;> >}> >else> >{> >cout <<>'Contains element or False'>;> >}> >return> 0;> }> |
>
>Producción
Contains element or False>
Consulte el final para el análisis de complejidad.
4. Para obtener/comprobar el tamaño de la cola de prioridad
Determina el tamaño de una cola de prioridad. En términos simples, el tamaño() El método se utiliza para obtener el número de elementos presentes en el Cola de prioridad .
A continuación se muestra el programa C++ para verificar el tamaño de la cola de prioridad:
C++
// C++ program to demonstrate the> // size() method of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >// create a priority queue of string> >priority_queue pqueue;> >// add items to priority_queue> >pqueue.push(>'Geeks'>);> >pqueue.push(>'for'>);> >pqueue.push(>'Geeks'>);> >pqueue.push(>'C++'>);> >// get the size of queue> >int> size = pqueue.size();> >cout <<>'Size of the queue: '> << size;> >return> 0;> }> |
>
>Producción
Size of the queue: 4>
Consulte el final para el análisis de complejidad.
5. Para intercambiar el contenido de una cola prioritaria con otra de tipo similar
Intercambio() La función se utiliza para intercambiar el contenido de una cola de prioridad con otra cola de prioridad del mismo tipo y del mismo o diferente tamaño.
A continuación se muestra el programa en C++ para intercambiar el contenido de una cola prioritaria con otra de tipo similar:
C++
// CPP program to illustrate> // Implementation of swap() function> #include> using> namespace> std;> // Print elements of priority queue> void> print(priority_queue<>int>>pq)> {> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >cout << endl;> }> int> main()> {> >// priority_queue container declaration> >priority_queue<>int>>pq1;> >priority_queue<>int>>pq2;> >// pushing elements into the 1st priority queue> >pq1.push(1);> >pq1.push(2);> >pq1.push(3);> >pq1.push(4);> >// pushing elements into the 2nd priority queue> >pq2.push(3);> >pq2.push(5);> >pq2.push(7);> >pq2.push(9);> >cout <<>'Before swapping:-'> << endl;> >cout <<>'Priority Queue 1 = '>;> >print(pq1);> >cout <<>'Priority Queue 2 = '>;> >print(pq2);> >// using swap() function to swap elements of priority> >// queues> >pq1.swap(pq2);> >cout << endl <<>'After swapping:-'> << endl;> >cout <<>'Priority Queue 1 = '>;> >print(pq1);> >cout <<>'Priority Queue 2 = '>;> >print(pq2);> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Producción
Before swapping:- Priority Queue 1 = 4 3 2 1 Priority Queue 2 = 9 7 5 3 After swapping:- Priority Queue 1 = 9 7 5 3 Priority Queue 2 = 4 3 2 1>
Consulte el final para el análisis de complejidad.
6. Para colocar un nuevo elemento en el contenedor de la cola de prioridad
Colocar() La función se utiliza para insertar un nuevo elemento en el contenedor de la cola de prioridad, el nuevo elemento se agrega a la cola de prioridad de acuerdo con su prioridad. Es similar a la operación de empuje. La diferencia es que la operación emplace() guarda una copia innecesaria del objeto.
A continuación se muestra el programa C++ para colocar un nuevo elemento en el contenedor de la cola de prioridad:
C++
// CPP program to illustrate> // Implementation of emplace() function> #include> using> namespace> std;> int> main()> {> >priority_queue<>int>>pq;> >pq.emplace(1);> >pq.emplace(2);> >pq.emplace(3);> >pq.emplace(4);> >pq.emplace(5);> >pq.emplace(6);> >// Priority queue becomes 1, 2, 3, 4, 5, 6> >// Printing the priority queue> >cout <<>'Priority Queue = '>;> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Producción
Priority Queue = 6 5 4 3 2 1>
Consulte el final para el análisis de complejidad.
7. Para representar el tipo de objeto almacenado como elemento en una cola_prioritaria
El método Priority_queue :: value_type es una función incorporada en C++ STL que representa el tipo de objeto almacenado como un elemento en Priority_queue. Actúa como sinónimo del parámetro de plantilla.
Sintaxis:
priority_queue::value_type variable_name>
A continuación se muestra el programa C++ para representar el tipo de objeto almacenado como elemento en una cola_prioritaria:
C++
// C++ program to illustrate the> // priority_queue :: value_type function> #include> using> namespace> std;> // Driver code> int> main()> {> >// declare integer value_type for priority queue> >priority_queue<>int>>::valor_tipo AnInt;> >// declare string value_type for priority queue> >priority_queue::value_type AString;> >// Declares priority_queues> >priority_queue<>int>>q1;> >priority_queue q2;> >// Here AnInt acts as a variable of int data type> >AnInt = 20;> >cout <<>'The value_type is AnInt = '> << AnInt << endl;> >q1.push(AnInt);> >AnInt = 30;> >q1.push(AnInt);> >cout <<>'Top element of the integer priority_queue is: '> ><< q1.top() << endl;> >// here AString acts as a variable of string data type> >AString =>'geek'>;> >cout << endl> ><<>'The value_type is AString = '> << AString> ><< endl;> >q2.push(AString);> >AString =>'for'>;> >q2.push(AString);> >AString =>'geeks'>;> >q2.push(AString);> >cout <<>'Top element of the string priority_queue is: '> ><< q2.top() << endl;> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Producción
The value_type is AnInt = 20 Top element of the integer priority_queue is: 30 The value_type is AString = geek Top element of the string priority_queue is: geeks>
Consulte el final para el análisis de complejidad.
Complejidades de todas las operaciones:
| Métodos | Complejidad del tiempo | Espacio Auxiliar |
|---|---|---|
| cola_prioridad::vacía() | O(1) | O(1) |
| cola_prioridad::tamaño() | O(1) | O(1) |
| cola_prioridad::arriba() | O(1) | O(1) |
| cola_prioridad::push() | O(logN) agregar cadena java | O(1) |
| cola_prioridad::pop() | O(logN) | O(1) |
| cola_prioridad::intercambio() | O(1) | EN) |
| prioridad_queue::emplazar() | O(logN) | O(1) |
| cola_prioridad tipo_valor | O(1) | O(1) |