A kupac olyan gyűjtemény, amely mindig ismeri a legkisebb elemét, és azt az elemet gyorsan ki is tudod venni belőle. Ez a természetes eszköz egy prioritási sorhoz: olyan várakozási sorhoz, amelyben a legfontosabb elem kerül sorra, nem pedig az, amelyik a legrégebb óta vár. A kupacok a heaps szókészletben találhatók.
Kupac építése
A <min-heap> egy üres kupacot épít, amelyből a legkisebb kulcs jön ki először; a <max-heap> ennek a tükörképe.
<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )
Elemek hozzáadása
Minden elem egy értékként tárolódik egy kulccsal együtt: a kulcs az a prioritás, amely szerint a Factor rendez. A heap-push ad hozzá egyet:
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
A kupac módosítható: a heap-push a helyén változtatja meg, nem pedig új kupacot ad vissza. A keep hasznos eszköz arra, hogy visszategyed a kupacot a veremre, miután a heap-push felemésztette.
Az első elem megtekintése és eltávolítása
A heap-peek visszaadja az első elemet, azaz a legkisebb kulcsú értéket, anélkül, hogy eltávolítaná. A heap-pop visszaadja ezt az elemet, és el is távolítja. A heap-empty? jelzi, maradt-e még valami, így tudod, mikor hagyd abba az elemek kiszedését. A heap-pop-all mindent egyszerre távolít el, és a { key value } párokból álló asszociációs listát adja vissza prioritási sorrendben.
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" } }
A heap-pop és a heap-empty? azok az építőelemek, amelyekkel egyszerre egy elemet tudsz kiszolgálni: nézd meg vagy vedd ki az elsőt, csinálj vele valamit, és állj meg, amint a heap-empty? t-t ad vissza. Az alábbi részfeladatok a heap-pop-all-t használják, hogy egy lépésben kiürítsék a teljes sort, de ugyanez a sorrend adódik abból is, ha addig szeded ki az elemeket, amíg a kupac ki nem ürül.
A heap-pop-all-ból származó párok egy asszociációs lista: a values (az assocs szókészletben) csak az értékeket tartja meg, a kulcsokat elhagyja.
Tanulófeladat
