Εισαγωγή
Ένα heap είναι μια συλλογή που ξέρει πάντα το μικρότερο στοιχείο της και σου
επιτρέπει να το βγάλεις γρήγορα. Είναι το φυσικό εργαλείο για μια ουρά
προτεραιότητας: μια σειρά αναμονής όπου εξυπηρετείται πρώτα το πιο σημαντικό
στοιχείο και όχι αυτό που περίμενε περισσότερο. Τα heap ζουν στο
heaps vocabulary.
Κατασκευή ενός heap
Το <min-heap> φτιάχνει ένα άδειο 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 είναι μεταβλητό: το heap-push το αλλάζει επί τόπου αντί να
επιστρέφει ένα νέο. Το keep είναι βολικό για να ξαναβάλεις το heap στη
στοίβα αφού το heap-push το έχει καταναλώσει.
Εξέταση και αφαίρεση του μπροστινού στοιχείου
Το heap-peek επιστρέφει το μπροστινό στοιχείο, δηλαδή την τιμή με το
μικρότερο κλειδί, χωρίς να το αφαιρεί. Το heap-pop επιστρέφει αυτό το
στοιχείο και το αφαιρεί. Το heap-empty? αναφέρει αν έχει μείνει κάτι, ώστε
να ξέρεις πότε να σταματήσεις να κάνεις pop. Το 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? είναι τα δομικά στοιχεία για να
εξυπηρετείς στοιχεία ένα ένα: κάνε peek ή pop στο μπροστινό, ενέργησε πάνω του
και σταμάτα μόλις το heap-empty? επιστρέψει t. Οι παρακάτω εργασίες
χρησιμοποιούν το heap-pop-all για να αδειάσουν ολόκληρη την ουρά σε ένα βήμα,
αλλά η ίδια σειρά προκύπτει αν κάνεις pop μέχρι να αδειάσει το heap.
Τα ζεύγη από το heap-pop-all είναι μια λίστα συσχέτισης: το values (στο
assocs) κρατά μόνο τις τιμές και πετάει τα κλειδιά.
Οδηγίες
Μια πολυάσχολη τράπεζα εξυπηρετεί τους πελάτες που περιμένουν με βάση την προτεραιότητα και όχι με τη σειρά που έφτασαν. Κάθε πελάτης παίρνει έναν αριθμό προτεραιότητας όταν παίρνει το νούμερό του, και ο ταμίας εξυπηρετεί πάντα επόμενο τον μικρότερο αριθμό (1 είναι ο πιο επείγων). Ένας min-heap είναι η ιδανική ουρά αναμονής.
1. Άνοιξε την ουρά
Όρισε τη new-queue, που δεν παίρνει τίποτα και επιστρέφει μια καινούρια, κενή ουρά προτεραιότητας.
new-queue
! => an empty priority queue
2. Πρόσθεσε έναν πελάτη
Όρισε τη join-queue, που παίρνει ένα όνομα πελάτη, έναν αριθμό προτεραιότητας και μια ουρά. Προσθέτει τον πελάτη στην ουρά και επιστρέφει την ουρά, ώστε οι πελάτες να προστίθενται ο ένας μετά τον άλλον.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
! => the queue, now holding alice (5) and bob (2)
3. Ποιος είναι ο επόμενος;
Όρισε τη next-name, που παίρνει μια ουρά και επιστρέφει το όνομα του πελάτη που πρέπει να εξυπηρετηθεί επόμενος, δηλαδή αυτού με τον μικρότερο αριθμό προτεραιότητας, χωρίς να τον αφαιρέσει.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue next-name .
! => "bob"
4. Εξυπηρέτησε όλους
Όρισε τη serve-all, που παίρνει μια ουρά και επιστρέφει τα ονόματα όλων των πελατών που περιμένουν, με τη σειρά που θα εξυπηρετούνταν.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
"carol" 9 rot join-queue serve-all .
! => { "bob" "alice" "carol" }
Άσκηση εκμάθησης
