Et le fait est qu'implémenter un conteneur générique n'est pas anodin.

On va voir ça. Mais si tu me le permets, avant je vais faire quelques commentaires:

Il y a des points positifs dans ton code. Par exemple l'existence de deux méthodes distinctes front et pop, c'est très bien. :)

friend ostream& operator << (ostream& os,Queue q);

est correct. Mais pour réduire les dépendances dans le code, on considère qu'il est mieux de déclarer global
ostream& operator << (ostream& os,Queue q);
et son corps est alors ainsi

ostream& operator << (ostream& os,Queue q)
{
	q.print();
}

Où print est évidemment une méthode public de Queue.

par contre

N'est pas très bon. Il faudrait:

void push(const Type&); 

La référence, c'est pour éviter une copie non voulue de l'item au moment du placement dans la queue. Le const est là pour éviter d'éventuelles erreurs de codage plus tard et pour permettre au compilateur d'effecteur des optimisations dans certaines situations.

Ceci:

Queue_Element<Type> *first; 
Queue_Element<Type> *last; 

Est annonciateur de problème. La finalité de ces membres semble être de servir à parcourir le contenu de la queue. C'est certainement un itérateur qu'il faudrait...

et là ça ne va plus du tout, nous arrivons sur le problème annoncé plus haut.

//sachant que la classe representant un element de la queue est: 
template <class Type> class Queue_Element {

Au départ tu essaies d'écrire une queue générique. c'est du moins ce que veux dire sa déclaration. Et un peu plus loin on voit que les éléments contenus ne peuvent pas être quelconques mais doivent détenir un pointeur sur le suivant, etc... et , ô hérésie, le type doit à l'avance connaître son conteneur puisque tu déclares la classe Queue amie de l'élément...
On dirait maintenant que tu codes une liste chaînée en C.
Mais plus du tout en C++ générique.
Donc avant de passer à ta queue à priorité, tu dois paufiner ta queue car elle ne marche pas en fait, contrairement à ce que tu semble penser. Elle en marche même pas du tout. Pardonne moi, mais c'est la réalité.
Elle marchera quand elle sera réellement générique, c'est à dire qu'il n'y aura aucune autre contrainte sur le type contenu autre le fait que son destructeur ne doive lever aucune exception.
Dans ce cas ta Queue fonctionnera peut être, si tant est que son code soit robuste aux exceptions, ce qu'il faudrait vérifier également.

Ceci fait tu pourrais passer à ta priory_queue (on dirait que tu t'exerces à ré-écrire le STL :) )

Basiquement et pour répondre enfin à ta question :) , une priority_queue est "tout simplement" (en théorie..) une queue donc le constructeur reçoit une fonction ou un objet fonction pour le tri des éléments. C'est donc relativement facile si la queue fonctionne. Mais cela implique probablement que la queue ait des iterateurs....

Bon courage. Tu t'es lancé dans un exercice ambitieux. Ecrire des conteneur génériques façon STL ça n'est pas de la tarte.... c'est même extrêmement difficile.

N'hésites pas à revenir sur ce forum, si tu en sens le besoin.