Купа - це колекція, яка завжди знає свій найменший елемент і дає змогу швидко його дістати. Це природний інструмент для пріоритетної черги: черги, у якій наступним обслуговують найважливіший елемент, а не той, що чекає найдовше. Купи живуть у словнику heaps.
Створення купи
<min-heap> створює порожню купу, з якої першим виходить найменший ключ, а <max-heap> - дзеркальне відображення цього.
<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )
Додавання елементів
Кожен елемент зберігається як значення разом із ключем, а ключ - це той пріоритет, за яким Factor їх упорядковує. heap-push додає один елемент:
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
Купа змінювана: heap-push змінює її на місці, а не повертає нову. keep стає в пригоді, щоб повернути купу на стек після того, як heap-push її спожив.
Перегляд і вилучення першого елемента
heap-peek повертає перший елемент, тобто значення з найменшим ключем, і при цьому не вилучає його. heap-pop повертає цей елемент і вилучає його. heap-empty? повідомляє, чи щось залишилося, тож ми знаємо, коли припинити вилучати елементи. heap-pop-all вилучає все одразу й повертає асоціативний список пар { key value } у порядку пріоритету.
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 і heap-empty? - це цеглинки, з яких складається обслуговування елементів по одному: зазирнути в перший елемент або вилучити його, щось із ним зробити й спинитися, щойно heap-empty? поверне t. У завданнях нижче ми скористаємося heap-pop-all, щоб спорожнити всю чергу за один крок, але той самий порядок вийде, якщо вилучати елементи, доки купа не спорожніє.
Пари з heap-pop-all - це асоціативний список: values (зі словника assocs) залишає лише значення, відкидаючи ключі.
Навчальна вправа
