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 fila de espera en la que se atiende primero al elemento más importante, no al 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 espejo.
<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )
Agregar elementos
Cada elemento se guarda como un valor junto con una clave; la clave es la prioridad según la cual ordena Factor. heap-push agrega 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 cambia en el lugar en vez de devolver uno nuevo. keep es útil para volver a poner el montículo en la pila después de que heap-push lo haya consumido.
Consultar y quitar el frente
heap-peek devuelve el elemento del frente (el valor con la clave más pequeña) sin quitarlo. heap-pop devuelve ese elemento y lo quita. heap-empty? te dice si queda algo, para que sepas cuándo dejar de quitar elementos. heap-pop-all quita 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 los bloques de construcción para servir elementos uno a uno: consulta o quita el frente, actúa sobre él y detente cuando heap-empty? devuelva t. Las tareas a continuación usan heap-pop-all para vaciar toda la cola en un solo paso, pero el mismo orden resulta de ir quitando elementos hasta que el montículo quede vacío.
Los pares que devuelve heap-pop-all son una lista de asociaciones: values (en assocs) conserva solo los valores y descarta las claves.
Instrucciones
Un banco muy concurrido atiende a los clientes en espera por prioridad, no en el orden en que llegaron. A cada cliente se le asigna un número de prioridad cuando toma un turno, y el cajero siempre atiende el número más bajo a continuación (1 es el más urgente). Un montículo mínimo es la fila 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. Agrega un cliente
Define join-queue, que recibe el nombre de un cliente, un número de prioridad y una cola. Agrega al cliente a la cola y devuelve la cola, así puedes agregar 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. ¿Quién sigue?
Define next-name, que recibe una cola y devuelve el nombre del cliente al que le toca ser atendido, el que tiene el menor número de prioridad, sin quitarlo 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
