6.3.90.900
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 #<leftist-tree [empty]>
> non-empty-tree-of-strings #<leftist-tree [count=4; min="a"]>
procedure
(leftist-tree? x) → boolean?
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
(leftist-tree-add t x) → leftist-tree?
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
(leftist-tree-add-all t xs) → leftist-tree?
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) #<leftist-tree [count=4; min="humble"]>
procedure
(leftist-tree-min t) → any/c
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
(leftist-tree->list t) → (listof any/c)
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
(in-leftist-tree t) → sequence?
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))
humble
radiant
some pig!
terrific