7.9

## Leftist Trees

 (require data/leftist-tree) package: leftist-tree

Leftist trees are immutable priority queues.

 procedure(leftist-tree <=? [xs]) → leftist-tree? <=? : (-> any/c any/c any/c) xs : sequence? = '()
Makes a new tree containing the elements of xs, ordered by <=?.

Examples:
 > (define empty-tree-of-strings (leftist-tree string<=?)) > (define non-empty-tree-of-strings (leftist-tree string<=? '("once" "upon" "a" "time"))) > empty-tree-of-strings # > non-empty-tree-of-strings #

 procedure x : any/c
Returns #t if x is a leftist tree, #f otherwise.

Examples:
 > (leftist-tree? (leftist-tree <=)) #t > (leftist-tree? "I can haz treaz?") #f

 procedure t : leftist-tree?
Returns #t if t is empty, #f otherwise.

Examples:
 > (define t (leftist-tree string<=?)) > (leftist-tree-empty? t) #t > (leftist-tree-empty? (leftist-tree-add t "κατέβην χθὲς εἰς Πειραιᾶ μετὰ Γλαύκωνος τοῦ Ἀρίστωνος...")) #f

 procedure t : leftist-tree?
Returns the number of elements in t.

Examples:
 > (define t (leftist-tree string<=?)) > (leftist-tree-count t) 0 > (leftist-tree-count (leftist-tree-add-all t (enum->list string/e 10))) 10

 procedure t : leftist-tree? x : any/c
Functionally extends t by adding x and returns the extended tree.

Examples:
 > (define empty (leftist-tree string<=?)) > (define non-empty (leftist-tree-add empty "Hello world!"))

 procedure t : leftist-tree? xs : sequence?
Functionally extends t by adding all elements of the sequence xs and returns the extended tree.

Examples:
 > (define empty (leftist-tree string<=?)) > (define words '("some pig!" "terrific" "radiant" "humble")) > (leftist-tree-add-all empty words) #

 procedure t : leftist-tree?
Returns the least element in t according to the tree’s ordering. If the tree is empty, an exception is raised.

Examples:
 > (define empty (leftist-tree string<=?)) > (define words '("some pig!" "terrific" "radiant" "humble")) > (leftist-tree-min (leftist-tree-add-all empty words)) "humble"

 procedure t : leftist-tree?
Functionally removes the least element in t and returns the fresh tree.

Examples:
 > (define empty (leftist-tree string<=?)) > (define words '("some pig!" "terrific" "radiant" "humble")) > (define full (leftist-tree-add-all empty words)) > (leftist-tree-count full) 4 > (leftist-tree-count (leftist-tree-remove-min full)) 3

 procedure t : leftist-tree?
Returns an ordered list of the elements of t.

Examples:
 > (define empty (leftist-tree string<=?)) > (define words '("some pig!" "terrific" "radiant" "humble")) > (define full (leftist-tree-add-all empty words)) > (leftist-tree->list full) '("humble" "radiant" "some pig!" "terrific")

 procedure t : leftist-tree?
Returns a sequence that generates the elements of t in order.

Examples:
> (define empty (leftist-tree string<=?))
> (define words '("some pig!" "terrific" "radiant" "humble"))
> (define full (leftist-tree-add-all empty words))
 > (for ([word (in-leftist-tree full)]) (displayln word))