Une file de priorité est une collection d’éléments possédant chacun un certain degré de priorité. L’opération d’extraction consiste à retirer de la file l’élément qui possède la plus grande priorité (ou l’un de ceux qui ont la priorité maximum).
La notion de file de priorité généralise les notions de pile et de file d’attente :
- Dans une pile, la priorité d’un élément est une fonction croissante de la date à laquelle il a été ajouté : le dernier élément entré est donc celui qui possède le plus grand degré de priorité.
- Dans une file d’attente, la priorité est une fonction décroissante de la date à laquelle l’élément a été ajouté : le premier entré (parmi ceux qui sont encore dans la file) est donc celui qui possède le plus grand degré de priorité.
On va voir trois façons différentes d’implémenter une file de priorité, mais avec un socle commun.
Dans tous les ca,s le type « file de priorité » de la façon suivante :
|
1 |
type 'a priofile = { data : 'a array; mutable n : int; prio : 'a -> 'a -> bool } |
Avec ces notations :
- le tableau
dataest destiné à recevoir les éléments de la file de priorité ; - le champ
ndonne le nombre d’éléments effectivement présents dans la file (et placés aux positions 0 à {n-1);} - l’expression
prio x yrenvoie true si la priorité de {x} est strictement supérieure à celle de {y(}et false sinon).
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres