Diaporama n°22¶

File de priorité, Tas¶

Rappel : File (classique)¶

"First In - First Out"

  • mettre_en_file(File, T) -> void
  • sortir_de_file(File) -> T
  • est_vide(File) -> bool

Exemple : tâches à accomplir

  • Trouver un sujet TIPE
  • Préparer la colle de maths
  • Faire les exercices de physique
  • Faire le DM d'informatique

FIFO ?

Exemple : tâches à accomplir avec un niveau de priorité

  • Trouver un sujet TIPE, à faire
  • Préparer la colle de maths, très urgent
  • Faire les exercices de physique, urgent
  • Faire le DM d'informatique, extrèmement urgent

Type de données abstrait FileDePriorité et opérations¶

  • Type paramétrique FilePrio<Prio,T> avec Prio type des priorités (souvent int), T type des tâches

  • création, destruction

  • ajouter(FilePrio,Prio,T) -> void

  • retirer_max(FilePrio) -> Prio, T

  • est_vide(FilePrio) -> bool

Implémentation possible (1)¶

Avec une liste de couples (priorité, tâche) non triée

  • liste chaînée ou tableau extensible

Complexité des opérations ?¶

  • ajouter en $\mathcal{O}(1)$
  • retirer_max en $\mathcal{O}(n)$ (on doit parcourir toute la liste)

Implémentation possible (2)¶

Avec une liste de couples (priorité, tâche) maintenue triée

  • liste chaînée ou tableau extensible

Complexité des opérations ?¶

  • ajouter en $\mathcal{O}(n)$ (insérer au bon endroit)
  • retirer_max en en $\mathcal{O}(1)$

Implémentation possible (3)¶

Avec un ABR équilibré

Complexité des opérations ?¶

  • ajouter en $\mathcal{O}(\log n)$
  • retirer_max en en $\mathcal{O}(\log n)$ (on va chercher à droite toute)

Implémentation avec un "Tas"¶

cf cours à suivre ...

Idée : secouer un tas de graviers

image.png

Les gros au-dessus, les petits en-dessous

Les gros au-dessus, les petits en-dessous

Un exemple de tas :

image.png