Ein Heap ist eine Sammlung, die immer ihr kleinstes Element kennt und aus der du dieses Element schnell entnehmen kannst. Er ist das natürliche Werkzeug für eine Prioritätswarteschlange: eine Warteschlange, in der das wichtigste Element als Nächstes bedient wird, nicht das, das am längsten gewartet hat. Heaps findest du im Vokabular heaps.
Einen Heap aufbauen
<min-heap> erzeugt einen leeren Heap, dessen kleinster Schlüssel zuerst herauskommt; <max-heap> ist das Spiegelbild.
<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )
Elemente hinzufügen
Jedes Element wird als Wert zusammen mit einem Schlüssel gespeichert, wobei der Schlüssel die Priorität ist, nach der Factor sortiert. heap-push fügt ein Element hinzu:
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
Ein Heap ist veränderlich: heap-push ändert ihn an Ort und Stelle, anstatt einen neuen zurückzugeben. keep ist praktisch, um den Heap wieder auf den Stack zu bekommen, nachdem heap-push ihn verbraucht hat.
Das vorderste Element ansehen und entfernen
heap-peek gibt das vorderste Element zurück: den Wert mit dem kleinsten Schlüssel, ohne ihn zu entfernen. heap-pop gibt dieses Element zurück und entfernt es. heap-empty? meldet, ob noch etwas übrig ist, damit du weißt, wann du mit dem Entfernen aufhören musst. heap-pop-all entfernt alles auf einmal und gibt eine Assoziationsliste von { key value }-Paaren in Prioritätsreihenfolge zurück.
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 und heap-empty? sind die Bausteine, um Elemente einzeln zu bedienen: Sieh dir das vorderste Element an oder entferne es, reagiere darauf und höre auf, sobald heap-empty? t zurückgibt. Die folgenden Aufgaben verwenden heap-pop-all, um die gesamte Warteschlange in einem Schritt zu leeren, aber dieselbe Reihenfolge ergibt sich, wenn du so lange Elemente entnimmst, bis der Heap leer ist.
Die Paare von heap-pop-all sind eine Assoziationsliste: values (in assocs) behält nur die Werte und lässt die Schlüssel weg.
Lernübung
