Le tas et la file de priorité
La file de priorité comme type abstrait et le tas binaire qui la réalise : propriété de tas, arbre complet rangé dans un tableau (indices du père et des fils), insertion par remontée, extraction par descente, coûts.
- 22 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Mises en situation
- Comprendre
Quelques cartes du deck
File de priorité : de quoi s'agit-il ?
Voir la réponse
Collection où l'on ajoute des éléments munis d'une priorité et où l'on retire toujours celui dont la priorité est la plus forte, quel que soit l'ordre d'arrivée.
À la différence d'une file ordinaire (premier arrivé, premier servi), l'ordre de sortie dépend de la priorité. Un tas la réalise avec ajout et extraction en O(log n).
Le tas minimum est
[2, 5, 3, 9, 6]. On y insère 1. Quel est le tableau obtenu ?[1, 5, 2, 9, 6, 3][1, 2, 3, 9, 6, 5][2, 5, 3, 9, 6, 1][1, 2, 5, 3, 9, 6]
Voir la réponse
[1, 5, 2, 9, 6, 3]1 se pose à l'indice 5, dont le père est à l'indice 2 (valeur 3) : échange. Il est alors à l'indice 2, dont le père est à l'indice 0 (valeur 2) : nouvel échange. Résultat : 1 à la racine, 2 à l'indice 2 et 3 à l'indice 5.
Dans un tas minimum, le plus petit élément se trouve toujours à la …, donc à l'indice … du tableau.
Voir la réponse
Dans un tas minimum, le plus petit élément se trouve toujours à la racine, donc à l'indice 0 du tableau.
Lire le minimum coûte donc O(1). L'extraire coûte O(log n), car il faut ensuite rétablir la propriété de tas.
Tas binaire : de quoi s'agit-il ?
Voir la réponse
Arbre binaire complet, rempli niveau par niveau de gauche à droite, où chaque nœud est plus petit que ses fils (tas minimum) ou plus grand (tas maximum).
Seule la racine est connue comme la plus petite (ou la plus grande) ; les frères ne sont pas ordonnés entre eux. Un tas n'est pas un tableau trié.
Un ordonnanceur garde 200 000 tâches en attente. À chaque nouvelle tâche, il retrie toute la liste par urgence, puis lance la plus urgente. Le serveur sature. Quelle réparation ?
- Ranger les tâches dans un tas ordonné par urgence
- Trier avec un tri plus rapide à chaque nouvelle tâche
- Ne retrier qu'une arrivée sur dix
- Ranger les tâches dans une liste chaînée triée
Voir la réponse
Ranger les tâches dans un tas ordonné par urgence
Un tri complet coûte O(n log n) à chaque arrivée, alors qu'on ne veut que la tâche la plus urgente. Un tas la donne en O(1), l'extrait et accueille une nouvelle tâche en O(log n). Une liste triée ferait l'insertion en O(n) ; un tri plus rapide garde le travail inutile, un tri moins fréquent lance parfois la mauvaise tâche.