Introduzione
«Heap» è una raccolta che conosce sempre il suo elemento più piccolo e ti permette di estrarlo rapidamente. È lo strumento naturale per una «coda con priorità»: una fila di attesa in cui viene servito per primo l'elemento più importante, non quello che ha aspettato più a lungo. Gli heap vivono nel vocabolario heaps.
Costruire un heap
<min-heap> costruisce un heap vuoto la cui chiave più piccola esce per prima; <max-heap> è l'immagine speculare.
<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )
Aggiungere elementi
Ogni elemento è memorizzato come un «valore» insieme a una «chiave»: la chiave è la priorità sulla quale Factor ordina. heap-push ne aggiunge uno:
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 heap è mutabile: heap-push lo modifica sul posto invece di restituirne uno nuovo. keep è comodo per riportare l'heap sullo stack dopo che heap-push lo ha consumato.
Esaminare e rimuovere l'elemento in testa
heap-peek restituisce l'elemento in testa, cioè il valore con la chiave più piccola, senza rimuoverlo. heap-pop restituisce quell'elemento e lo rimuove. heap-empty? indica se è rimasto qualcosa, così sai quando smettere di estrarre elementi. heap-pop-all rimuove tutto in una volta, restituendo una lista di associazioni di coppie { key value } in ordine di 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 e heap-empty? sono gli elementi costitutivi per servire gli elementi uno alla volta: esamina o estrai la testa, agisci di conseguenza e fermati quando heap-empty? restituisce t. Le attività che seguono usano heap-pop-all per svuotare l'intera coda in un solo passaggio, ma lo stesso ordine si ottiene estraendo finché l'heap non è vuoto.
Le coppie prodotte da heap-pop-all sono una «lista di associazioni»: values (in assocs) conserva solo i valori, scartando le chiavi.
Istruzioni
Una banca molto impegnata serve i clienti in attesa in base alla priorità, non nell'ordine in cui sono arrivati. Ogni cliente riceve un numero di priorità quando prende un biglietto, e il cassiere serve sempre per primo il numero più basso (1 è il più urgente). Un min-heap è la coda d'attesa perfetta.
1. Apri la coda
Definisci new-queue, che non prende nulla e restituisce una coda a priorità nuova e vuota.
new-queue
! => an empty priority queue
2. Aggiungi un cliente
Definisci join-queue, che prende il nome di un cliente, un numero di priorità e una coda. Aggiunge il cliente alla coda e restituisce la coda, così i clienti si possono aggiungere uno dopo l'altro.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
! => the queue, now holding alice (5) and bob (2)
3. Chi è il prossimo?
Definisci next-name, che prende una coda e restituisce il nome del cliente che dovrebbe essere servito per prossimo, quello con il numero di priorità più basso, senza rimuoverlo.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue next-name .
! => "bob"
4. Servi tutti
Definisci serve-all, che prende una coda e restituisce i nomi di tutti i clienti in attesa, nell'ordine in cui verrebbero serviti.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
"carol" 9 rot join-queue serve-all .
! => { "bob" "alice" "carol" }
Esercizio di apprendimento
