Ejercicio usando Colas en C++

[xKuZz]

El motivo por el que los introduce ya ordenados es porque utiliza un heap (también conocido como lund, o montículo en español y eso es un árbol binario que representa a un conjunto ordenado, en este caso la relación de prioridad, y el padre siempre es mayor siguiendo dicha relación que los hijos y los hijos menores que el padre dicho brevemente. Para saber más sobre el tema pídele ayuda a tu buscador favorito).

Utilizar esto implica conocer dicha relación de orden desde el principio. Traducido a eficiencia eso quiere decir que las operaciones son:

O(1) para top(), size(), empty()
O(log n) para push(x), pop().

Por lo que como puedes ver realiza sus operaciones de manera muy eficiente. Por si no te habías dado cuenta, cuando no hay una función de prioridad definida al crear la cola automáticamente coge el operador menor para el tipo de datos que existe. De hecho si no existiese el operador menor para int te habría dado un error en tiempo de compilación.

En conclusión:
a) No le tengas miedo a hacer functores, hay varias maneras, cada cual con su ventajas y sus inconvenientes, la más usual es la primera que te he puesto, no es para nada complejo familiarízate con ella y con la STL, porque si sigues con C++ en la universidad, créeme que te hará mucha falta saber usar ambos con soltura y suele ser más eficiente que hacer la implementación nosotros mismos.

b) Si realmente necesitas hacerlo de otra manera, utiliza otra estructura de datos como el vector, deque, la que veas conveniente para solventar el problema de la manera que quieres, o incluso reutiliza alguna que hayas creado en el pasado, pero no priority_queue.