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 {fija ordenar}).
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.
Liza
Las listas son contenedores de secuencias que permiten la asignación de memoria no contigua. En comparación con el vector, la lista tiene un recorrido lento, pero una vez que se ha encontrado una posición, la inserción y la eliminación son rápidas. Normalmente, cuando decimos una Lista, hablamos de una lista doblemente enlazada. Para implementar una lista de enlace simple, usamos una lista de reenvío.
Funciones utilizadas con Listas:
- push_front(x): Agrega un nuevo elemento ‘x’ al principio de la lista.
- push_back(x): Agrega un nuevo elemento ‘x’ al final de la lista.
Listas de reenvío
La lista de reenvío en STL implementa una lista enlazada individualmente. Introducidas desde C++ 11, las listas de reenvío son más útiles que otros contenedores en las operaciones de inserción, eliminación y movimiento (como ordenar) y permiten la inserción y eliminación constante de elementos en el tiempo. la listala la la la dela una al revés
la la
Funciones utilizadas con la lista de reenvío:
- push_front(x): Agrega un nuevo elemento ‘x’ al principio de la lista.
Este artículo se centra en cómo se puede usar la cola de prioridad de la lista de reenvío y la lista en C++. La cola de prioridad de listas y listas de reenvío puede ser bastante útil al diseñar estructuras de datos complejas.
A continuación se muestra la implementación de la cola de prioridad de la lista de reenvío:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority queue
// contents. Deliberately passing it
// call by value since we don't want
// to remove elements from the priority
// queue
void print(priority_queue<forward_list<int> > priorityQueue)
{
while (!priorityQueue.empty()) {
// Each element of the priority
// queue is a forward list itself
forward_list<int> st = priorityQueue.top();
cout << "[ ";
// Print the forward list elements
for (auto element : st)
cout << element << ' ';
cout << ']';
cout << '\n';
// Pop out the topmost forward
// list
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Declaring a priority queue of
// forward list
priority_queue<forward_list<int> > priorityQueue;
// Declaring a forward list
forward_list<int> forwardList1;
// Inserting into the forward list
forwardList1.push_front(2);
forwardList1.push_front(4);
forwardList1.push_front(6);
// Inserting the forward list into
// the priority queue
priorityQueue.push(forwardList1);
// Declaring another forward list
forward_list<int> forwardList2;
// Inserting into the forward list
forwardList2.push_front(1);
forwardList2.push_front(3);
forwardList2.push_front(7);
// Inserting the forward list into
// the priority queue
priorityQueue.push(forwardList2);
// Declaring another forward list
forward_list<int> forwardList3;
// Inserting into the forward list
forwardList3.push_front(11);
forwardList3.push_front(22);
forwardList3.push_front(33);
// Inserting the forward list into
// the priority queue
priorityQueue.push(forwardList3);
// Calling print function
print(priorityQueue);
return 0;
}
[ 33 22 11 ] [ 7 3 1 ] [ 6 4 2 ]
A continuación se muestra la implementación de la cola de prioridad de listas:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print priority queue
// contents. Deliberately passing it
// call by value since we don't want
// to remove elements from the priority
// queue
void print(priority_queue<list<int> > priorityQueue)
{
while (!priorityQueue.empty()) {
// Each element of the priority
// queue is a list itself
list<int> st = priorityQueue.top();
cout << "[ ";
// Print the list elements
for (auto element : st)
cout << element << ' ';
cout << ']';
cout << '\n';
// Pop out the topmost list
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Declaring a priority queue of
// lists
priority_queue<list<int> > priorityQueue;
// Declaring a list
list<int> list1;
// Inserting into the list
// Pushing at the front in the
list1.push_front(2);
// Pushing at the back in the
// list
list1.push_back(4);
list1.push_back(6);
// Inserting the list into the
// priority queue
priorityQueue.push(list1);
// Declaring another list
list<int> list2;
// Inserting into the list
// Pushing at the front in the
list2.push_front(2);
// Pushing at the back in the
// list
list2.push_back(4);
list2.push_back(7);
// Inserting the list into the
// priority queue
priorityQueue.push(list2);
// Declaring another list
list<int> list3;
// Inserting into the list
// Pushing at the front in the
list3.push_front(11);
// Pushing at the back in the
// list
list3.push_back(22);
list3.push_back(33);
// Inserting the list into the
// priority queue
priorityQueue.push(list3);
// Calling print function
print(priorityQueue);
return 0;
}
[ 11 22 33 ] [ 2 4 7 ] [ 2 4 6 ]
Por defecto, la cola de prioridad es un montón máximo, por lo tanto, internamente para dos listas/listas de reenvío dentro de la cola de prioridad, la lista/lista de reenvío que tiene el primer elemento mayor es el elemento superior. Si el primer elemento es igual, se compara el segundo valor de la lista/lista de reenvío y así sucesivamente.