Utilisation d’un tableau non trié

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 :

Avec ces notations :

  • le tableau data est destiné à recevoir les éléments de la file de priorité ;
  • le champ n donne le nombre d’éléments effectivement présents dans la file (et placés aux positions 0 à {n-1);}
  • l’expression prio x y renvoie true si la priorité de {x} est strictement supérieure à celle de {y(}et false sinon).
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :