¿Cómo se implementa la cola prioritaria en C ++? ¿Cómo se hace usando STL?

Una implementación decente de una cola prioritaria que usa la biblioteca estándar se puede encontrar en la biblioteca estándar misma.

El estándar define una plantilla de clase llamada “prioridad_queue” (ver §23.6.4). Esta plantilla de clase representa una implementación canónica de una cola prioritaria: un montón binario construido en la parte superior de una matriz.

Aquí está mi versión simplificada (he omitido definiciones de tipos y constructores, pero todo lo demás es una cita directa del estándar):

plantilla ,
clase Compare = std :: less >
clase priority_queue {
protegido:
Contenedor c;
Comparar comp;

público:
prioridad_queue explícita (const Container & c_ = Container (),
const Compare & comp_ = Comparar ())
: c (c_), comp (comp_)
{
std :: make_heap (c.begin (), c.end (), comp);
}

bool empty () const {return c.empty (); }
std :: size_t size () const {return c.size (); }

const T & top () const {return c.front (); }

empuje vacío (const T & x)
{
c.push_back (x);
std :: push_heap (c.begin (), c.end (), comp);
}

void pop ()
{
std :: pop_heap (c.begin (), c.end (), comp);
c.pop_back ();
}
};

Este código es bastante sencillo, especialmente si ya está familiarizado con los montones binarios.

El parámetro de plantilla T especifica un tipo de elementos almacenados en la cola. El parámetro Container especifica el contenedor que se usa para almacenar elementos (es std::vector de forma predeterminada, pero se puede usar cualquier contenedor de secuencia con iterador de acceso aleatorio y operaciones front() , push_back() y pop_back() ). Por último, Compare especifica el comparador: std::less le da una cola de prioridad orientada al máximo, std::greater le da una cola orientada al mínimo.

En el constructor std::make_heap() convierte el contenido de un contenedor dado en un montón. La forma en que lo hace está definida por la implementación, pero generalmente se utiliza una variación del algoritmo basado en la separación por tiempo lineal. Si no está familiarizado con los algoritmos de almacenamiento dinámico binario, considere consultar con su libro favorito. O eche un vistazo a la implementación real (busque el método make_heap ).

El método top() devuelve un elemento superior.

El método push() agrega un elemento a la cola. Primero, push() agrega el elemento dado al final del contenedor. Luego, std::push_heap() propaga por la cola hasta que esté en el lugar correcto usando el algoritmo de cribado. Nuevamente, es posible que desee consultar con un libro o la implementación (busque push_heap ).

Finalmente, el método pop() elimina el elemento superior de la cola. La llamada a std::pop_heap() mueve el elemento superior al final del contenedor intercambiándolo con el último y luego “heapifica” el resto de los contenidos usando el viejo y bueno tamizado. Después de eso, pop_back() elimina el último elemento.

Y esto es más o menos cómo se implementa una cola prioritaria en C ++.

Una cola de prioridad es una cola en la que cada elemento de la cola tiene su propia prioridad, de modo que la cola siempre se ordena por prioridad y, por lo tanto, todos los elementos se procesan en orden de prioridad.

Dicho esto, una implementación ingenua (fuerza bruta) sería clasificar los elementos en la cola cada vez que llega un nuevo elemento.

Una mejora con respecto a eso sería buscar binariamente la posición que debería tener.

La mejor implementación que conozco es usar un montón. Colas de prioridad

La mejor implementación de montón que conozco utiliza una matriz debajo: una implementación de matriz de un montón

Bueno, estaba buscando lo mismo para poder usar una implementación de cola de prioridad simple en C ++, pero no pude encontrar ninguna implementación simple ya que la mayoría de los estudiantes carecen de una buena comprensión de STL y las plantillas que codifiqué para mí según la explicación proporcionada en CLRS es bastante simple y no le agregué muchas funciones, solo funciones simples que pueden mostrarle la lógica de las colas de prioridad. Comenté mi código lo suficiente para que no se confunda

#pragma una vez
#include
usando el espacio de nombres estándar;

plantilla // que define la clase de plantilla
clase Priority_q
{
// ————————- variables ——————- \\

privado: item * Quee; // haciendo una matriz del elemento de plantilla en el que quiero construir una cola prioritaria
// antes que nada, haciendo un montón
// luego convertir el montón en una cola prioritaria
privado: tamaño int; // contiene el tamaño de la clase
privado: int last_index = -1; // muestra el último elemento en el montón

// ———————— constructores ———————- \\
public: Priority_q ();

public: Priority_q (int size);

// ———————– Métodos ———————- \\

public: item peek (); // devuelve el elemento en

// ———– empujar ————\\

public: bool push (entrada de ítem); // agregar un elemento a la cola prioritaria

public: item pop (); // conseguir la cabeza de la reina

privado: bool Priority_q :: max_heapify (int index); // esto hace un montón en la matriz

};

plantilla
bool Priority_q :: max_heapify (int index) // esto hace un montón en la matriz
{

int left = 2 * index + 1;
int right = 2 * index + 2;

if (left> last_index) // index es de hecho una raíz, por lo que está en el lugar correcto
falso retorno;

if (right> last_index) // marcando el elemento secundario correcto
derecha = -1; // establecer un centinela

// es un poco complicado porque estoy trabajando con plantillas

int más grande = índice; // mayor es el índice de los elementos más grandes entre índice, derecha e izquierda
// ofcours si tu más grande no cambia después de comparar no es necesario recursivo

if (Quee [izquierda] {// muestra que el montón no está arreglado
swap (Quee [izquierda], Quee [índice]);
mayor = izquierda;
}

if (right! = -1) // ofc deberíamos comprobar si este nodo tiene un hijo correcto
if (Quee [right] ” debería sobrecargarse para cada clase que desee utilizar
{// muestra que el montón no está arreglado
swap (Quee [derecha], Quee [índice]);
mayor = derecha;
}
// ahora comprobando si el más grande ha cambiado
if (índice == mayor)
volver verdadero;
return max_heapify (el más grande);

}

plantilla
item Priority_q :: peek () // devuelve el elemento en
{
devolver Quee [0]; // ofc si su prioridad de cambio quee se atornilla
}

plantilla
bool Priority_q :: push (entrada de elemento) // agregando un elemento a la cola de prioridad
{
if (last_index == tamaño)
falso retorno; // muestra que no tengo lugar para esta entrada
last_index ++;
Quee [last_index] = input;
para (int i = (last_index + 1) / 2; i> = 0; i–)
max_heapify (i);
volver verdadero;

}

plantilla
item Priority_q :: pop () // obteniendo el encabezado de la cola
{
if (last_index == -1)
devuelve NULL;
elemento temp = Quee [0];
swap (Quee [0], Quee [last_index]);
last_index–;
// arreglando el montón de nuevo
para (int i = (last_index + 1) / 2; i> = 0; i–)
max_heapify (i);
temperatura de retorno;

}

plantilla
Priority_q :: Priority_q ()
{ // Constructor predeterminado
tamaño = 1;
Quee = nuevo elemento [2]; // bueno meh
}

plantilla
Priority_q :: Priority_q (int size)
{// si sueles usar esto en un programa realmente bueno, comprueba el tamaño y, obviamente, no debería ser negativo
esto-> tamaño = tamaño;
Quee = nuevo elemento [tamaño]; // asignación igual al tamaño de entrada

}