Introdução
Um heap é uma coleção que sempre sabe qual é o seu menor item e permite retirar esse item rapidamente. É a ferramenta natural para uma fila de prioridade: uma fila de espera em que o item mais importante é atendido primeiro, e não o que esperou mais tempo. Os heaps ficam no vocabulário heaps.
Construindo um heap
<min-heap> cria um heap vazio cuja menor chave sai primeiro; <max-heap> é a imagem espelhada.
<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )
Adicionando itens
Cada item é armazenado como um valor junto com uma chave: a chave é a prioridade pela qual o Factor ordena. heap-push adiciona um item:
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: heap-push o altera no lugar em vez de retornar um novo. keep é útil para trazer o heap de volta para a pilha depois que heap-push o consumiu.
Consultando e removendo o elemento da frente
heap-peek retorna o item da frente (o valor com a menor chave) sem removê-lo. heap-pop retorna esse item e o remove. heap-empty? informa se ainda resta alguma coisa, para você saber quando parar de fazer pop. heap-pop-all remove tudo de uma vez e retorna uma lista de associações de pares { key value } em 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" } }
heap-pop e heap-empty? são os blocos de construção para atender itens um de cada vez: faça peek ou pop da frente, aja sobre o item e pare quando heap-empty? retornar t. As tarefas abaixo usam heap-pop-all para esvaziar toda a fila de uma só vez, mas a mesma ordem resulta de fazer pop até o heap ficar vazio.
Os pares de heap-pop-all formam uma lista de associações: values (em assocs) mantém apenas os valores, descartando as chaves.
Instruções
Um banco movimentado atende os clientes que esperam por prioridade, e não na ordem em que chegaram. Cada cliente recebe um número de prioridade ao pegar uma senha, e o caixa sempre atende o menor número em seguida (1 é o mais urgente). Um heap mínimo é a fila de espera perfeita.
1. Abra a fila
Defina new-queue, que não recebe nada e retorna uma fila de prioridade nova e vazia.
new-queue
! => an empty priority queue
2. Adicione um cliente
Defina join-queue, que recebe o nome de um cliente, um número de prioridade e uma fila. Ela adiciona o cliente à fila e retorna a fila, para que os clientes possam ser adicionados um depois do outro.
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?
Defina next-name, que recebe uma fila e retorna o nome do cliente que deve ser atendido em seguida, aquele com o menor número de prioridade, sem removê-lo.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue next-name .
! => "bob"
4. Atenda todo mundo
Defina serve-all, que recebe uma fila e retorna os nomes de todos os clientes que estão esperando, 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
