Introducción
Un montículo es una colección que siempre conoce su elemento más
pequeño y te permite sacarlo rápidamente. Es la herramienta natural
para una cola de prioridad: una cola de espera en la que se atiende
primero el elemento más importante, no el que lleva más tiempo
esperando. Los montículos viven en el vocabulario heaps.
Construir un montículo
<min-heap> construye un montículo vacío cuya clave más pequeña sale
primero; <max-heap> es su imagen especular.
<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )
Añadir elementos
Cada elemento se guarda como un valor junto con una clave: la clave
es la prioridad que Factor usa para ordenar. heap-push añade 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 montículo es mutable: heap-push lo modifica in situ en lugar de
devolver uno nuevo. keep resulta práctico para volver a poner el
montículo en la pila después de que heap-push lo haya consumido.
heap-peek devuelve el elemento del frente (el valor con la clave más
pequeña) sin extraerlo. heap-pop devuelve ese elemento y lo
extrae. heap-empty? indica si queda algo, para que sepas cuándo dejar
de extraer. heap-pop-all elimina todo de una vez y devuelve una lista
de asociaciones de pares { key value } en orden de prioridad.
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 y heap-empty? son las piezas básicas para servir
elementos de uno en uno: consulta el frente o extráelo, actúa sobre él
y para en cuanto heap-empty? devuelva t. Las tareas de abajo usan
heap-pop-all para vaciar toda la cola de un solo paso, pero el mismo
orden se obtiene extrayendo hasta que el montículo esté vacío.
Los pares que devuelve heap-pop-all son una lista de asociaciones:
values (de assocs) conserva solo los valores y descarta las claves.
Instrucciones
Un banco con mucha afluencia atiende a los clientes que esperan por prioridad en lugar de por orden de llegada. A cada cliente se le asigna un número de prioridad cuando coge un tique, y el cajero siempre atiende a continuación al cliente con el número más bajo (1 es el más urgente). Un montículo mínimo es la cola de espera perfecta.
1. Abre la cola
Define new-queue, que no recibe nada y devuelve una cola de prioridad nueva y vacía.
new-queue
! => an empty priority queue
2. Añade un cliente
Define join-queue, que recibe el nombre de un cliente, un número de prioridad y una cola. Añade el cliente a la cola y devuelve la cola, de modo que se pueden añadir clientes uno tras otro.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
! => the queue, now holding alice (5) and bob (2)
3. ¿A quién le toca?
Define next-name, que recibe una cola y devuelve el nombre del cliente al que hay que atender a continuación, el que tiene el número de prioridad más bajo, sin eliminarlo de la cola.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue next-name .
! => "bob"
4. Atiende a todos
Define serve-all, que recibe una cola y devuelve los nombres de todos los clientes en espera, en el orden en que serían atendidos.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
"carol" 9 rot join-queue serve-all .
! => { "bob" "alice" "carol" }
Ejercicio de aprendizaje
