Files de priorité

Une file de priorite est une structure de donnees qui gere les adjonctions et les suppressions selon la discipline suivante : lors d’une arrivee, le client se presente avec une valeur representant une priorite (definie sur un ensemble dote d’une relation d’ordre total tel que les entiers naturels comme c’est le cas ici) ; lors d’une suppression, l’element qui a la plus forte priorite est supprime de la file. Par convention ici, plus l’element est petit plus la priorite est grande. En cas de conflit lors d’une suppression (cas ou plusieurs candidats ont la meme plus forte priorite), le choix de l’elu n’est pas precise par la specification. Les operations suivantes sont definies : f p Vide(), operation qui delivre une file de priorite vide ; f p Ajout(v, f), operation d’adjonction de la priorite v qui delivre une file de priorite resultant de l’ajout de la priorite v dans la file f ; f p Prio(f), operation qui delivre (sans la supprimer de la file f) la valeur prioritaire. Cette operation est preconditionnee par le fait que f ne soit pas vide ; f p Supp(f), operation qui delivre une file de priorite identique a la file f a l’exception d’une occurrence de la valeur prioritaire de f qui est supprimee. Cette operation est preconditionnee par le fait que f ne soit pas vide ; f p EstV ide(f), operation qui delivre la valeur true si et seulement si la file f ne contient aucun element.