Leftist Trees

6.2.901.900

top ← prev up next →

Leftist Trees

Jon Zeppieri <zeppieri@gmail.com>

(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
(leftist-tree-empty? t) → leftist-tree?
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
(leftist-tree-count t) → exact-nonnegative-integer?
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
(leftist-tree-remove-min t) → leftist-tree?
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

top ← prev up next →