Cómo usar C ++ Priority_Queue?

En C ++, una cola es una estructura de datos de la lista donde el primer elemento que se coloca en la lista es el primer elemento que se eliminará, cuando la eliminación se realizará. Una cola prioritaria en C ++ es similar, pero tiene algún orden; Es el elemento con el mayor valor que se elimina primero. La cola prioritaria aún se puede configurar para que sea el elemento con el menor valor que se elimina primero. Cualquier cola debe tener al menos la empujar() función y el estallido() función. El empujar() la función agrega un nuevo elemento en la parte posterior. Para la cola normal, la estallido() la función elimina el primer elemento jamás empujado. Para la cola prioritaria, la estallido() La función elimina el elemento con la más alta prioridad, que podría ser la más grande o más pequeña, dependiendo del esquema de pedido.

Para usar la prioridad C ++, el programa debe comenzar con un código como:

#incluir
#incluir
usando el espacio de nombres STD;

Incluye la biblioteca de cola en el programa.

Para continuar leyendo, el lector debería haber tenido un conocimiento básico de C++.

Contenido del artículo

• Construcción básica
• Funciones de miembro importantes
• Otras funciones de cola prioritaria
• Datos de cadena
• Otras construcciones de colas prioritarias
• Conclusión

Construcción básica

La estructura de datos debe construirse primero antes de que pueda usarse. La construcción aquí significa instanciar un objeto de la clase de cola de la biblioteca. El objeto de cola debe tener un nombre dado por el programador. La sintaxis más simple para crear una cola de prioridad es:

prioridad_queue raro nombre;

Con esta sintaxis, el mayor valor se elimina primero. Un ejemplo de la instanciación es:

prioridad_queue pq;

o

prioridad_queue pq;

El vector y el deque son dos estructuras de datos en c++. Se puede crear una prioridad_queue con cualquiera de ellos. La sintaxis para crear una cola prioritaria a partir de la estructura vectorial es:

prioridad_queue, comparar> pq;

Un ejemplo de esta instanciación es:

prioridad_queue, menos > pq;

Observe la brecha entre> y> al final de la declaración. Esto es para evitar confusión con >>. El código de comparación predeterminado es "menor", lo que significa el mejor, y no necesariamente el primer valor, se eliminaría primero. Entonces, la declaración de creación se puede escribir simplemente como:

prioridad_queue > pq;

Si primero se eliminará el menor valor, entonces la declaración debe ser:

prioridad_queue, mayor que > pq;

Funciones de miembro importantes

La función push ()
Esta función empuja un valor, que es su argumento, a la prioridad_queue. Devuelve nulo. El siguiente código ilustra esto:

prioridad_queue pq;
pq.empuje (10);
pq.empuje (30);
pq.empuje (20);
pq.empuje (50);
pq.empuje (40);

Esta prioridad_queue ha recibido 5 valores enteros en el orden de 10, 30, 20, 50, 40. Si todos estos elementos van a salir de la cola prioritaria, entonces saldrán en el orden de 50, 40, 30, 20, 10.

La función pop ()
Esta función elimina de la prioridad_queue el valor con la más alta prioridad. Si el código de comparación es "mayor", eliminará el elemento con el valor más pequeño. Si se llama nuevamente, elimina el siguiente elemento con el valor más pequeño del resto; llamado nuevamente, elimina el siguiente valor más pequeño presente, y así sucesivamente. Devuelve nulo. El siguiente código ilustra esto:

prioridad_queue, mayor que > pq;
pq.push ('a');
pq.push ('c');
pq.push ('b');
pq.push ('e');
pq.push ('d');

Tenga en cuenta que para llamar a una función de miembro, el nombre del objeto debe ser seguido por un punto, y luego la función.

La función superior ()
El estallido() la función elimina el siguiente valor de la más alta prioridad, pero no lo devuelve, como estallido() es una función vacía. Utilizar el arriba() función para conocer el valor de la más alta prioridad que debe eliminarse a continuación. El arriba() La función devuelve una copia del valor de la más alta prioridad en la prioridad_queue. El siguiente código, donde el siguiente valor de la más alta prioridad es el menor valor, ilustra esto

prioridad_queue, mayor que > pq;
pq.push ('a'); pq.push ('c'); pq.push ('b'); pq.push ('e'); pq.push ('d');
char ch1 = pq.arriba(); pq.estallido();
char ch2 = pq.arriba(); pq.estallido();
Char CH3 = PQ.arriba(); pq.estallido();
char ch4 = PQ.arriba(); pq.estallido();
char ch5 = PQ.arriba(); pq.estallido();
cout<

La salida es 'a "b" c "d" e'.

La función vacía ()
Si un programador usa el arriba() función en una prioridad vacía_queue, después de la compilación exitosa, recibiría un mensaje de error como:

Falla de segmentación (núcleo arrojado)

Entonces, siempre verifique si la cola prioritaria no está vacía antes de usar el arriba() función. El vacío() La función miembro devuelve un bool, verdadero, si la cola está vacía y falsa si la cola no está vacía. El siguiente código ilustra esto:

prioridad_queue pq;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.empuje (i1); pq.empuje (i2); pq.empuje (i3); pq.empuje (i4); pq.empuje (i5);
mientras(!pq.vacío())

cout << pq.top() << ";
pq.estallido();

cout << '\n';

Otras funciones de cola prioritaria

La función size ()
Esta función devuelve la longitud de la cola de prioridad, como lo ilustra el siguiente código:

prioridad_queue pq;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.empuje (i1); pq.empuje (i2); pq.empuje (i3); pq.empuje (i4); pq.empuje (i5);
int len ​​= PQ.tamaño();
cout << len << '\n';

La salida es 5.

La función swap ()
Si dos Priority_Queues son del mismo tipo y tamaño, entonces pueden ser intercambiados por esta función, como muestra el siguiente código:

prioridad_queue PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.empuje (i1); PQ1.empuje (i2); PQ1.empuje (i3); PQ1.empuje (i4); PQ1.empuje (i5);
prioridad_queue PQA;
int it1 = 1; int it2 = 3; int it3 = 2; int it4 = 5; int it5 = 4;
PQA.empuje (it1); PQA.empuje (it2); PQA.empuje (it3); PQA.empuje (it4); PQA.empuje (it5);
PQ1.intercambio (PQA);
mientras(!PQ1.vacío())

cout << pq1.top() << ";
PQ1.estallido();
cout<<'\n';
mientras(!PQA.vacío())

cout << pqA.top() << ";
PQA.estallido();
cout<<'\n';

La salida es:

5 4 3 2 1
50 40 30 20 10

La fuction emplace ()
El Emplace () la función es similar a la función de empuje. El siguiente código ilustra esto:

prioridad_queue PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.Emplace (i1);
PQ1.Emplace (i2);
PQ1.Emplace (i3);
PQ1.Emplace (i4);
PQ1.Emplace (i5);
mientras(!PQ1.vacío())

cout << pq1.top() << ";
PQ1.estallido();
cout<<'\n';

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:

#incluir
prioridad_queue PQ1;
String S1 = String ("Pen"),
s2 = string ("lápiz"),
S3 = String ("Libro de ejercicios"),
S4 = String ("Libro de texto"),
s5 = string ("regla");
PQ1.empuje (s1);
PQ1.empuje (s2);
PQ1.empuje (s3);
PQ1.empuje (S4);
PQ1.empuje (S5);
mientras(!PQ1.vacío())

cout << pq1.top() << " ";
PQ1.estallido();
cout<<'\n';

La salida es:

Libro de texto Regla Lápiz Pen Ejercicio Libro

Otras construcciones de colas prioritarias

Creación explícita de un vector
Se puede crear una cola prioritaria explícitamente a partir de un vector como muestra el siguiente código:

#incluir
vector vtr = 10, 30, 20, 50, 40;
prioridad_queue PQ (VTR.begin (), VTR.fin());
mientras(!pq.vacío())

cout << pq.top() << ";
pq.estallido();
cout<<'\n';

La salida es: 50 40 30 20 10. Esta vez, el encabezado de vector también debe incluirse. Los argumentos para la función del constructor toman los punteros de inicio y finalización del vector. El tipo de datos para el vector y el tipo de datos para priority_queue debe ser el mismo.

Para darle menos valor a la prioridad, la declaración para el constructor sería:

prioridad_queue, mayor> int >> pq (vtr.begin (), VTR.fin());

Creación explícita a partir de una matriz
Se puede crear una cola prioritaria explícitamente a partir de una matriz como muestra el siguiente código:

int arr [] = 10, 30, 20, 50, 40;
prioridad_queue PQ (arr, arr+5);
mientras(!pq.vacío())

cout << pq.top() << ";
pq.estallido();
cout<<'\n';

La salida es: 50 40 30 20 10. Los argumentos para la función del constructor toman los punteros de inicio y finalización de la matriz. ARR Devuelve el puntero de inicio, "ARR+5" Devuelve el puntero justo después de la matriz, y 5 es del tamaño de la matriz. El tipo de datos para la matriz y el tipo de datos para priority_queue debe ser el mismo.

Para darle menos valor a la prioridad, la declaración para el constructor sería:

prioridad_queue, mayor que > pq (arr, arr+5);

NOTA: En C ++, la prioridad_queue en realidad se llama adaptador, no solo un contenedor.

Código de comparación personalizado

Tener todos los valores en la cola de prioridad ascendente o todos descendientes 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. Esto es seguido por dos números: 86 y 87, que son menos de 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 inferiores a 86. Los números 79 y 74 son inferiores a 87. Los números 80 y 81 son inferiores a 84. Los números 64 y 69 son inferiores a 79.

La colocación de los números sigue los criterios máximo de montón - ver más tarde. Para proporcionar dicho esquema para la prioridad_queue, el programador debe proporcionar su propio código de comparación; ver más tarde.

Conclusión

Un C ++ Priority_Queue es una cola de primera salida. La función miembro, empujar(), agrega un nuevo valor a la cola. La función miembro, arriba(), lee el valor superior en la cola. La función miembro, estallido(), elimina sin devolver el valor superior de la cola. La función miembro, vacío(), verifica si la cola está vacía. Sin embargo, la prioridad_queue difiere de la cola, en eso, sigue algún algoritmo de prioridad. Puede ser mayor, desde el primer hasta el último, o menos, del primero hasta el último. Los criterios (algoritmo) también pueden estar definidos por el programador.