Introdução
Um heap é uma coleção que sabe sempre qual é o menor dos seus itens e que te permite retirá-lo depressa. É a ferramenta natural para uma fila de prioridade: uma fila de espera onde é servido a seguir o item mais importante, e não o que esperou mais tempo. Os heaps fazem parte do vocabulário heaps.
Construir um heap
<min-heap> cria um heap vazio de onde sai primeiro a menor chave; <max-heap> é o seu espelho.
<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )
Adicionar itens
Cada item é guardado como um valor junto com uma chave: a chave é a prioridade segundo a qual o Factor ordena. O heap-push acrescenta um:
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
Um heap é mutável: o heap-push altera-o no próprio local em vez de devolver um novo. O keep é útil para trazer o heap de volta para a pilha depois de heap-push o ter consumido.
Consultar e remover o item da frente
O heap-peek devolve o item da frente, ou seja, o valor com a menor chave, sem o remover. O heap-pop devolve esse item e remove-o. O heap-empty? indica se ainda resta alguma coisa, para saberes quando parar de retirar itens. O heap-pop-all remove tudo de uma vez e devolve uma lista de associações de pares { key value } pela ordem de prioridade.
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" } }
O heap-pop e o heap-empty? são os blocos de construção para servir itens um a um: consulta ou retira o item da frente, age sobre ele e acaba assim que heap-empty? devolver t. As tarefas abaixo usam o heap-pop-all para esvaziar a fila toda num só passo, mas a mesma ordem surge se fores retirando itens até o heap ficar vazio.
Os pares devolvidos por heap-pop-all são uma lista de associações: o values (em assocs) fica só com os valores e descarta as chaves.
Instruções
Um banco movimentado atende os clientes em espera por prioridade e não pela ordem por que chegaram. Cada cliente recebe um número de prioridade quando tira uma senha, e o funcionário do balcão atende sempre a seguir o número mais baixo (1 é o mais urgente). Uma min-heap é a fila de espera perfeita.
1. Abre a fila
Define new-queue, que não recebe nada e devolve uma fila de prioridade nova e vazia.
new-queue
! => an empty priority queue
2. Adiciona um cliente
Define join-queue, que recebe o nome de um cliente, um número de prioridade e uma fila. Adiciona o cliente à fila e devolve a fila, para que se possam adicionar clientes uns a seguir aos outros.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
! => the queue, now holding alice (5) and bob (2)
3. Quem é o próximo?
Define next-name, que recebe uma fila e devolve o nome do cliente que deve ser atendido a seguir (o que tem o número de prioridade mais baixo), sem o remover.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue next-name .
! => "bob"
4. Atende todos
Define serve-all, que recebe uma fila e devolve os nomes de todos os clientes em espera, na ordem em que seriam atendidos.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
"carol" 9 rot join-queue serve-all .
! => { "bob" "alice" "carol" }
Exercício de aprendizagem
