Introduction
Un tas est une collection qui connaît toujours son plus petit élément et qui permet de le retirer rapidement. C'est l'outil naturel pour une file de priorité : une file d'attente où c'est l'élément le plus important qui passe en premier, et non celui qui a attendu le plus longtemps. Les tas se trouvent dans le vocabulaire heaps.
Construis un tas
<min-heap> construit un tas vide dont la plus petite clé sort en premier ; <max-heap> en est l'image miroir.
<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )
Ajoute des éléments
Chaque élément est stocké sous forme d'une valeur associée à une clé, la clé étant la priorité selon laquelle Factor trie les éléments. heap-push en ajoute un :
heap-push ( value key heap -- )
USING: heaps ;
<min-heap>
"alice" 5 pick heap-push ! value "alice", priority 5
"bob" 2 pick heap-push ! value "bob", priority 2
Un tas est mutable : heap-push le modifie sur place au lieu de renvoyer un nouveau tas. keep est bien pratique pour récupérer le tas sur la pile une fois que heap-push l'a consommé.
Consulte et retire l'élément de tête
heap-peek renvoie l'élément de tête, c'est-à-dire la valeur ayant la plus petite clé, sans le retirer. heap-pop renvoie cet élément et le retire. heap-empty? indique s'il reste quelque chose, ce qui te permet de savoir quand arrêter de dépiler. heap-pop-all retire tout d'un coup et renvoie une liste d'associations de paires { key value } dans l'ordre de priorité.
heap-peek ( heap -- value key )
heap-pop ( heap -- value key )
heap-empty? ( heap -- ? )
heap-pop-all ( heap -- alist )
USING: assocs heaps kernel prettyprint ;
<min-heap>
"alice" 5 pick heap-push
"bob" 2 pick heap-push
dup heap-empty? . ! => f (two items waiting)
dup heap-peek drop . ! => "bob" (smallest key, still in the heap)
dup heap-pop drop . ! => "bob" (smallest key, now removed)
heap-pop-all . ! => { { 5 "alice" } }
heap-pop et heap-empty? sont les briques de base pour servir les éléments un par un : on regarde ou on retire l'élément de tête, on agit dessus, et on s'arrête dès que heap-empty? renvoie t. Les tâches ci-dessous utilisent heap-pop-all pour vider toute la file en une seule étape, mais on obtient le même ordre en dépilant jusqu'à ce que le tas soit vide.
Les paires renvoyées par heap-pop-all forment une liste d'associations : values (dans assocs) ne garde que les valeurs et laisse tomber les clés.
Instructions
Une banque bien occupée sert les clients qui attendent par priorité, plutôt que dans l'ordre d'arrivée. Chaque client reçoit un numéro de priorité au moment où il prend un ticket, et le guichetier sert toujours le numéro le plus bas (1 est le plus urgent). Un tas min est la file d'attente idéale.
1. Ouvre la file
Définis new-queue, qui ne prend rien et renvoie une nouvelle file de priorité vide.
new-queue
! => an empty priority queue
2. Ajoute un client
Définis join-queue, qui prend un nom de client, un numéro de priorité et une file. Il ajoute le client à la file et renvoie la file, ce qui permet d'ajouter les clients les uns après les autres.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
! => the queue, now holding alice (5) and bob (2)
3. Qui est le suivant ?
Définis next-name, qui prend une file et renvoie le nom du client qui doit être servi ensuite, celui dont le numéro de priorité est le plus bas, sans le retirer.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue next-name .
! => "bob"
4. Sers tout le monde
Définis serve-all, qui prend une file et renvoie les noms de tous les clients en attente, dans l'ordre dans lequel ils seraient servis.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
"carol" 9 rot join-queue serve-all .
! => { "bob" "alice" "carol" }
Exercice d'apprentissage
