Cola de prioridades (STL priority_queue)

La cola de prioridades es una estructura de datos que se puede visualizar como una bolsa, donde podemos ir metiendo elementos uno atrás del otro, pero sólo los podemos retirar según un criterio de prioridad. Por ejemplo, en el caso de un ladrón obsesivo-compulsivo, podría robar un banco cargando bolsas de dinero sin ningún criterio, y al vaciarla podría retirar los billetes según su valor (primero los de $100, luego los de $50, etc.).

Otro ejemplo, imaginemos que tenemos un barco:

#include <queue>
#include <list>

using namespace std;

class Barco {
public:
  void subirPasajero(const Pasajero& pasajero);
  void abandonarBarco(list<Pasajero>& pasajerosEnOrden);

private:
  priority_queue<Pasajero> pasajeros_;
};

La función subirPasajero() debe agregar un pasajero al barco, y abandonarBarco() debe sacar todos los pasajeros del barco y colocarlos (por orden de prioridad) en la lista que se recibe como argumento:

void Barco::subirPasajero(const Pasajero& pasajero)
{
  pasajeros_.push(pasajero);
}

void Barco::abandonarBarco(list<Pasajero>& pasajerosEnOrden)
{
  while (!pasajeros_.empty()) {
    pasajerosEnOrden.push_back(pasajeros_.top());
    pasajeros_.pop();
  }
}

Tenga en cuenta que la función miembro pop() de las colas en C++ (queue, priority_queue, etc.) no retornan el valor extraído. Esto es así para evitar crear copias de los objetos dentro de la cola. De este modo la función top() devuelve una referencia al elemento mismo que se encuentra en la cola, y pop() lo remueve sin devolver nada. Así nos evitamos de crear copias temporales de la instancia removida.

Para poder usar la priority_queue sobre un tipo de dato propio (como Pasajero), debemos ofrecer una implementación del operator<() para comparar distintas instancias de nuestro tipo de dato (este operador se utiliza para saber qué elemento debe salir último de la cola, es decir, el menor elemento tiene menor prioridad):

enum Prioridad { Capitan, Hombre, Mujer, Ninio };

class Pasajero {
public:
  Pasajero(Prioridad p) : prioridad_(p) { }

  bool operator<(const Pasajero& otro) const {
    return prioridad_ < otro.prioridad_;
  }

  Prioridad prioridad() const { return prioridad_; }

private:
  Prioridad prioridad_;
};

De este modo, el capitán tiene prioridad 0 y es tomado en cuenta como el de menor prioridad para abandonar el barco. Los pasajeros que mayor prioridad tienen de abandonar el barco son las mujeres y los niños. En este caso podrían tener igual prioridad, no tendría mucho sentido salvar a todos los niños sin sus respectivas madres.

Ahora podemos crear un ejemplo:

#include <iostream>

using namespace std;

int main()
{
  Barco titanic;
  titanic.subirPasajero(Pasajero(Capitan));
  titanic.subirPasajero(Pasajero(Mujer));
  titanic.subirPasajero(Pasajero(Hombre));
  titanic.subirPasajero(Pasajero(Mujer));
  titanic.subirPasajero(Pasajero(Ninio));
  titanic.subirPasajero(Pasajero(Hombre));
  titanic.subirPasajero(Pasajero(Ninio));
  // ...

  list<Pasajero> pasajeros;
  titanic.abandonarBarco(pasajeros);
  
  for (list<Pasajero>::iterator it = pasajeros.begin(),
         end = pasajeros.end(); it != end; ++it) {
    cout << it->prioridad() << "\n";
  }
  
  return 0;
}

El anterior ejemplo imprime:

3
3
2
2
1
1
0

Lo que significa que, sin importar el orden en el cual agregamos los pasajeros, primero extraemos los niños, luego las mujeres, los hombres, y finalmente el capitán.

Más información:
http://www.cplusplus.com/reference/stl/priority_queue/
http://en.wikipedia.org/wiki/Priority_queue