Para usar el priority_queue de C ++, el programa debe comenzar con un código como:
#incluir
#incluir
utilizando espacio de nombreshoras;
Incluye la biblioteca de colas en el programa.
Para continuar leyendo, el lector debe tener un conocimiento básico de C ++.
Contenido del artículo
- Construcción básica
- Funciones importantes de los miembros
- Otras funciones de cola de prioridad
- Datos de cadena
- Otras construcciones de colas de prioridad
- Conclusión
Construcción básica
La estructura de datos debe construirse primero antes de que pueda utilizarse. La construcción aquí significa instanciar un objeto de la clase de cola de la biblioteca. A continuación, el programador debe asignar un nombre al objeto de cola. La sintaxis más simple para crear una cola de prioridad es:
cola_prioridad<escribe>queueName;
Con esta sintaxis, primero se elimina el valor más grande. Un ejemplo de instanciación es:
cola_prioridad<En t>pq;o
cola_prioridad<carbonizarse>pq;
El vector y la deque son dos estructuras de datos en C ++. Se puede crear un priority_queue con cualquiera de ellos. La sintaxis para crear una cola de prioridad a partir de la estructura vectorial es:
cola_prioridad<tipo, vector<el mismo tipo>, comparar>pq;Un ejemplo de esta instanciación es:
cola_prioridad<En t, vector<En t>, menos<En t> >pq;Observe el espacio entre> y> al final de la declaración. Esto es para evitar confusiones con >>. El código de comparación predeterminado es menor, lo que significa que el mayor, y no necesariamente el primer valor, se eliminaría primero. Entonces, la declaración de creación se puede escribir simplemente como:
cola_prioridad<En t, vector<En t> >pq;Si el valor mínimo debe eliminarse primero, entonces la declaración debe ser:
cola_prioridad<En t, vector<En t>, mayor que<En t> >pq;Funciones importantes de los miembros
La función push ()
Esta función empuja un valor, que es su argumento, a priority_queue. Vuelve vacío. El siguiente código ilustra esto:
pq.empujar(10);
pq.empujar(30);
pq.empujar(20);
pq.empujar(50);
pq.empujar(40);
Este priority_queue ha recibido 5 valores enteros en el orden de 10, 30, 20, 50, 40. Si todos estos elementos se van a sacar de la cola de prioridad, saldrán en el orden de 50, 40, 30, 20, 10.
La función pop ()
Esta función elimina de priority_queue el valor con la prioridad más alta. Si el código de comparación es mayor, eliminará el elemento con el valor más pequeño. Si se vuelve a llamar, elimina el siguiente elemento con el valor más pequeño del resto; llamado de nuevo, elimina el siguiente valor más pequeño presente, y así sucesivamente. Vuelve vacío. El siguiente código ilustra esto:
pq.empujar('a');pq.empujar('c');pq.empujar('b');pq.empujar('Y');pq.empujar('D');
Tenga en cuenta que para llamar a una función miembro, el nombre del objeto debe ir seguido de un punto y luego la función.
La función top ()
los pop() La función elimina el siguiente valor de mayor prioridad, pero no lo devuelve, ya que pop() es una función nula. Utilizar el cima() función para conocer el valor de máxima prioridad que debe eliminarse a continuación. los cima() La función devuelve una copia del valor de mayor prioridad en priority_queue. El siguiente código, donde el siguiente valor de mayor prioridad es el menor valor, ilustra esto
pq.empujar('a');pq.empujar('c');pq.empujar('b');pq.empujar('Y');pq.empujar('D');
carbonizarsech1=pq.cima();pq.pop();
carbonizarsech2=pq.cima();pq.pop();
carbonizarsech3=pq.cima();pq.pop();
carbonizarsech4=pq.cima();pq.pop();
carbonizarsech5=pq.cima();pq.pop();
costo<<ch1<<' '<<ch2<<' '<<ch3<<' '<<ch4<<' '<<ch5<<' orte';
La salida es 'a' 'b' 'c' 'd' 'e'.
La función vacía ()
Si un programador usa el cima() función en un priority_queue vacío, después de la compilación exitosa, recibiría un mensaje de error como:
Por lo tanto, siempre verifique si la cola de prioridad no está vacía antes de usar el cima() función. los vacío() La función miembro devuelve un valor bool, verdadero, si la cola está vacía, y falso si la cola no está vacía. El siguiente código ilustra esto:
cola_prioridad<En t>pq;En ti1= 10; En ti2= 30; En ti3= 20; En ti4= 50; En ti5= 40;
pq.empujar(i1);pq.empujar(i2);pq.empujar(i3);pq.empujar(i4);pq.empujar(i5);
tiempo(!pq.vacío())
{
costo <<pq.cima() << ' ';
pq.pop();
}
costo << ' orte';
Otras funciones de cola de prioridad
La función size ()
Esta función devuelve la longitud de la cola de prioridad, como lo ilustra el siguiente código:
En ti1= 10; En ti2= 30; En ti3= 20; En ti4= 50; En ti5= 40;
pq.empujar(i1);pq.empujar(i2);pq.empujar(i3);pq.empujar(i4);pq.empujar(i5);
En tlen=pq.Talla();
costo <<len<< ' orte';
La salida es 5.
La función swap ()
Si dos priority_queues son del mismo tipo y tamaño, esta función puede intercambiarlas, como muestra el siguiente código:
En ti1= 10; En ti2= 30; En ti3= 20; En ti4= 50; En ti5= 40;
pq1.empujar(i1);pq1.empujar(i2);pq1.empujar(i3);pq1.empujar(i4);pq1.empujar(i5);
cola_prioridad<En t>pqA;
En tit1= 1; En tit2= 3; En tit3= 2; En tit4= 5; En tit5= 4;
pqA.empujar(it1);pqA.empujar(it2);pqA.empujar(it3);pqA.empujar(it4);pqA.empujar(it5);
pq1.intercambio(pqA);
tiempo(!pq1.vacío())
{
costo <<pq1.cima() << ' ';
pq1.pop();
} costo<<' orte';
tiempo(!pqA.vacío())
{
costo <<pqA.cima() << ' ';
pqA.pop();
} costo<<' orte';
La salida es:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
La función emplace ()
los emplazamiento () La función es similar a la función de empujar. El siguiente código ilustra esto:
En ti1= 10; En ti2= 30; En ti3= 20; En ti4= 50; En ti5= 40;
pq1.emplazamiento(i1);pq1.emplazamiento(i2);pq1.emplazamiento(i3);pq1.emplazamiento(i4);pq1.emplazamiento(i5);
tiempo(!pq1.vacío())
{
costo <<pq1.cima() << ' ';
pq1.pop();
} costo<<' orte';
La salida es:
50 40 30 20 10
Datos de cadena
Al comparar cadenas, se debe usar la clase de cadena y no el uso directo de los literales de cadena porque compararía punteros y no las cadenas reales. El siguiente código muestra cómo se usa la clase de cadena:
#incluircola_prioridad<cuerda>pq1;
cadena s1=cuerda('lápiz'), s2=cuerda('lápiz'), s3=cuerda('libro de ejercicios'), s4=cuerda('libro de texto'), s5=cuerda('regla');
pq1.empujar(s1);pq1.empujar(s2);pq1.empujar(s3);pq1.empujar(s4);pq1.empujar(s5);
tiempo(!pq1.vacío())
{
costo <<pq1.cima() << ' ';
pq1.pop();
} costo<<' orte';
La salida es:
& emsp; libro de texto & emsp; regla & emsp; lápiz & emsp; bolígrafo & emsp; cuaderno de ejercicios
Otras construcciones de colas de prioridad
Creación explícita a partir de un vector
Se puede crear una cola de prioridad explícitamente a partir de un vector, como muestra el siguiente código:
vector<En t>vtr= {10,30,20,50,40};
cola_prioridad<En t>pq(vtr.empezar(), vtr.fin());
tiempo(!pq.vacío())
{
costo <<pq.cima() << ' ';
pq.pop();
} costo<<' orte';
La salida es: 50 40 30 20 10. Esta vez, también se debe incluir el encabezado vectorial. Los argumentos de la función constructora toman los punteros inicial y final del vector. El tipo de datos para el vector y el tipo de datos para priority_queue deben ser iguales.
Para hacer que el valor mínimo sea la prioridad, la declaración para el constructor sería:
cola_prioridad<En t, vector<En t>, mayor que>En t> >pq(vtr.empezar(), vtr.fin()); Creación explícita a partir de una matriz
Se puede crear una cola de prioridad explícitamente a partir de una matriz, como muestra el siguiente código:
cola_prioridad<En t>pq(arr, arr+5);
tiempo(!pq.vacío())
{
costo <<pq.cima() << ' ';
pq.pop();
} costo<<' orte';
La salida es: 50 40 30 20 10. Los argumentos de la función constructora toman los punteros de inicio y final de la matriz. arr devuelve el puntero de inicio, arr + 5 devuelve el puntero justo después de la matriz y 5 es el tamaño de la matriz. El tipo de datos de la matriz y el tipo de datos de priority_queue deben ser iguales.
Para hacer que el valor mínimo sea la prioridad, la declaración para el constructor sería:
cola_prioridad<En t, vector<En t>, mayor que<En t> >pq(arr, arr+5);Nota: En C ++, priority_queue en realidad se llama adaptador, no solo contenedor.
Código de comparación personalizado
Tener todos los valores en la cola de prioridad ascendente o descendente no es la única opción para la cola de prioridad. Por ejemplo, una lista de 11 enteros para un montón máximo es:
88, 86, 87, 84, 82, 79,74, 80, 81, , , 64, 69
El valor más alto es 88. A esto le siguen dos números: 86 y 87, que son menores que 88. El resto de los números son menores que estos tres números, pero no realmente en orden. Hay dos celdas vacías en la lista. Los números 84 y 82 son menores que 86. Los números 79 y 74 son menores que 87. Los números 80 y 81 son menores que 84. Los números 64 y 69 son menores que 79.
La ubicación de los números sigue los criterios de pila máxima; consulte más adelante. Con el fin de proporcionar un esquema de este tipo para priority_queue, el programador debe proporcionar su propio código de comparación, ver más adelante.
Conclusión
Un priority_queue de C ++ es una cola de primero en entrar, primero en salir. La función miembro, empujar(), agrega un nuevo valor a la cola. La función miembro, cima(), lee el valor superior de la cola. La función miembro, pop(), elimina sin devolver el valor superior de la cola. La función miembro, vacío(), comprueba si la cola está vacía. Sin embargo, priority_queue se diferencia de la cola en que sigue algún algoritmo de prioridad. Puede ser mayor, del primero al último, o menor, del primero al último. Los criterios (algoritmo) también pueden ser definidos por el programador.