9 Treap

Treaps are binary search trees in which each node has both a search key and a priority. Its keys are sorted in inorder and its each node priority is smaller than the priorities of its children. Because of this, a treap is a binary search tree for the keys and a heap for its priorities. This implementation uses random priorities to achieve good average-case performance.

Provides worst case running time of O(log(n)) for the operations insert , find-min/max and delete-min/max .

syntax
( Treap A)

A treap of type A.

procedure
( treap compa...)→(Treap A)
comp:(AA->Boolean)
a:A

Function treap creates a Treap with the given inputs. Elements are assigned a random priority between from 0 to 1.

Example:

> (treap <123456)

- : #(struct:Treap

((-> Positive-Byte Positive-Byte Boolean)

(U (Node Positive-Byte) Null)

Integer))

#<Treap>

In the above example, the treap obtained will have elements 1 thru’ 6 with < as the comparison function.

procedure
( empty? treap)→Boolean
treap:(Treap A)

Function empty? checks if the given treap is empty or not.

Examples:

> (empty? (treap<123456))

- : Boolean

#f
> (empty? (treap<))

- : Boolean

#t

procedure
( contains? atreap)→Boolean
a:A
treap:(Treap A)

Function contains? takes an element and a treap and checks whether or not that element is contained within the treap.

Examples:

> (contains? 4(treap<123456))

- : Boolean

#t
> (contains? 4(treap<123567))

- : Boolean

#f

Added in version 0.1 of package pfds.

procedure
( insert atreap)→(Treap A)
a:A
treap:(Treap A)

Function insert takes an element and a treap and inserts the given element into the treap with a random priority between 0 and 1.

Example:

> (insert 10(treap<123))

- : #(struct:Treap

((-> Positive-Byte Positive-Byte Boolean)

(U (Node Positive-Byte) Null)

Integer))

#<Treap>

In the above example, insert adds the element 10 to (treap<123).

procedure
( find-min/max treap)→A
treap:(Treap A)

Function find-min/max takes a treap and gives the largest or the smallest element in the treap if treap is not empty else throws an error. The element returned is largest or smallest depends on the comparison function of the treap.

Examples:

> (find-min/max (treap<123456))

- : Integer [more precisely: Positive-Byte]

1
> (find-min/max (treap>123456))

- : Integer [more precisely: Positive-Byte]

6
> (find-min/max (treap<))

find-min/max: given treap is empty

procedure
( delete-min/max treap)→(Treap A)
treap:(Treap A)

Function delete-min/max takes a treap and returns the same treap without the min or max element in the given treap. The element removed from the treap is max or min depends on the comparison function of the treap.

Examples:

> (delete-min/max (treap<123456))

- : #(struct:Treap

((-> Positive-Byte Positive-Byte Boolean)

(U (Node Positive-Byte) Null)

Integer))

#<Treap>
> (delete-min/max (treap>123456))

- : #(struct:Treap

((-> Positive-Byte Positive-Byte Boolean)

(U (Node Positive-Byte) Null)

Integer))

#<Treap>
> (delete-min/max (treap<))

delete-min/max: given treap is empty

In the above example, (delete-min/max (treap<123456)), deletes the element 1(min) from the treap. And (delete-min/max (treap>123456)), deletes the element 6(max) from the treap.

procedure
( delete elemtreap)→(Treap A)
elem:A
treap:(Treap A)

Function delete deletes the given element from the given treap.

Examples:

> (delete 6(treap<123456))

- : #(struct:Treap

((-> Positive-Byte Positive-Byte Boolean)

(U (Node Positive-Byte) Null)

Integer))

#<Treap>
> (delete 3(treap>123456))

- : #(struct:Treap

((-> Positive-Byte Positive-Byte Boolean)

(U (Node Positive-Byte) Null)

Integer))

#<Treap>
> (delete 10(treap<))

eval:17:0: Type Checker: Polymorphic function `delete' could

not be applied to arguments:

Argument 1:

Expected: A

Given:Positive-Byte

Argument 2:

Expected: #(struct:Treap ((-> A A Boolean) (U (Node A)

Null) Integer))

Given:#(struct:Treap ((-> Nothing Nothing Boolean) (U

(Node Nothing) Null) Integer))

in: <

In the above example, (delete 6(treap<123456)), deletes the 6 returns (treap<12345). And (delete 3(treap>123456)) returns (treap>12456).

procedure
( treap->list treap)→(ListofA)
treap:(Treap A)

Function treap->list takes a treap and returns a list which is sorted according to the comparison function of the treap.

Examples:

> (treap->list (treap>123456))

- : (Listof Positive-Byte)

'(5 6 2 4 3 1)
> (treap->list (treap<123456))

- : (Listof Positive-Byte)

'(2 1 3 4 5 6)

procedure
( map comparerfunctreap1treap2...)→(Treap A)
comparer:(CC->Boolean)
func:(AB...B->C)
treap1:(Treap A)
treap2:(Treap B)

Function map is similar to map for lists.

Examples:

> (treap->list (map <add1(treap <123456)))

- : (Listof Positive-Index)

'(3 2 7 5 4 6)
> (treap->list (map <*(treap <123456)(treap <123456)))

- : (Listof Positive-Index)

'(5 2 24 24 6 15)

procedure
( fold funcinittreap1treap2...)→C
func:(CAB...B->C)
init:C
treap1:(Treap A)
treap2:(Treap B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold +0(treap <123456))

- : Integer [more precisely: Nonnegative-Integer]

21
> (fold *1(treap <123456)(treap <123456))

- : Integer [more precisely: Positive-Integer]

518400

procedure
( filter functreap)→(Treap A)
func:(A->Boolean)
treap:(Treap A)

Function filter is similar to filter .

Examples:

> (definetrp(treap<123456))
> (treap->list (filter (λ:([x:Integer])(>x5))trp))

- : (Listof Positive-Byte)

'(6)
> (treap->list (filter (λ:([x:Integer])(<x5))trp))

- : (Listof Positive-Byte)

'(2 1 3 4)
> (treap->list (filter (λ:([x:Integer])(<=x5))trp))

- : (Listof Positive-Byte)

'(5 3 2 1 4)

procedure
( remove functreap)→(Treap A)
func:(A->Boolean)
treap:(Treap A)

Function remove is similar to filter but remove removes the elements which satisfy the predicate.

Examples:

> (treap->list (remove (λ:([x:Integer])(>x5))
(treap<123456)))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

> (treap->list (remove (λ:([x:Integer])(<x5))
(treap<123456)))

- : (Listof Positive-Byte)

'(6 5)

> (treap->list (remove (λ:([x:Integer])(<=x5))
(treap<123456)))

- : (Listof Positive-Byte)

'(6)

procedure
( andmap functreap1treap2...)→Boolean
func:(AB...B->Boolean)
treap1:(Treap A)
treap2:(Treap B)

Function andmap is similar to andmap .

Examples:

> (andmap even?(treap <123456))

- : Boolean

#f
> (andmap odd?(treap <123456))

- : Boolean

#f
> (andmap positive?(treap <123456))

- : Boolean

#t
> (andmap negative?(treap <-1-2))

- : Boolean

#t

procedure
( ormap functreap1treap2...)→Boolean
func:(AB...B->Boolean)
treap1:(Treap A)
treap2:(Treap B)

Function ormap is similar to ormap .

Examples:

> (ormap even?(treap <123456))

- : Boolean

#t
> (ormap odd?(treap <123456))

- : Boolean

#t
> (ormap positive?(treap <-1-234-56))

- : Boolean

#t
> (ormap negative?(treap <1-2))

- : Boolean

#t

procedure
( build-treap sizefunccomp)→(Treap A)
size:Natural
func:(Natural->A)
comp:(AA->Boolean)

Function build-treap is similar to build-list but this function takes an extra comparison function.

Examples:

> (treap->list (build-treap 5(λ:([x:Integer])(add1x))<))

- : (Listof Integer)

'(5 1 2 3 4)
> (treap->list (build-treap 5(λ:([x:Integer])(*xx))<))

- : (Listof Integer)

'(4 0 1 16 9)

9.1Priorities🔗 i

The following functions allow the user to manipulate node priorities. Treaps containing nodes with manually set priorities cannot guarantee O(log(n)) running times, and care should be taken in selecting appropriate priorities if one wants to avoid O(n) running times.

procedure
( treap/priority compa...)→(Treap A)
comp:(AA->Boolean)
a:(PairofAReal)

Function treap creates a Treap with the given inputs each assigned the priority they are paired with.

Example:

> (treap/priority <'(1. 3)'(2. 2)'(3. 8)'(4. 7)'(5. 1)'(6. 4))

- : #(struct:Treap

((-> Positive-Byte Positive-Byte Boolean)

(U (Node Positive-Byte) Null)

Integer))

#<Treap>

In the above example, the treap obtained will have elements 1 thru 6 with < as the comparison function.

Added in version 0.1 of package pfds.

procedure
( insert/priority aprioritytreap)→(Treap A)
a:A
priority:Real
treap:(Treap A)

Function insert takes an element, priority and a treap and inserts the given element into the treap with a specified priority.

Examples:

> (insert/priority 10-4(treap<123))

- : #(struct:Treap

((-> Positive-Byte Positive-Byte Boolean)

(U (Node Positive-Byte) Null)

Integer))

#<Treap>
> (root (insert/priority 10-4(treap<123)))

- : Integer [more precisely: Positive-Byte]

10
> (root (insert/priority 104(treap<123)))

- : Integer [more precisely: Positive-Byte]

1

In the above examples, insert/priority adds the element 10 to (treap<123) with varying priorities.

Added in version 0.1 of package pfds.

procedure
( root treap)→A
treap:(Treap A)

Function root returns the value of the node at the root of the given treap.

Examples:

> (root (treap<123))

- : Integer [more precisely: Positive-Byte]

1
> (root (treap/priority symbol<?'(a. 4)'(b. 7)'(c. 2)))

- : Symbol

'c

The root node is always the node with the lowest priority.

Added in version 0.1 of package pfds.

procedure
( root/priority treap)→Real
treap:(Treap A)

Function root/priority gives the priority of the root node in the given treap, which is the smallest priority in the treap.

Example:

> (root/priority (treap/priority symbol<?'(a. 4)'(b. 7)'(c. 2)))

- : Real

2

Added in version 0.1 of package pfds.

procedure
( delete-root treap)→(Treap A)
treap:(Treap A)

Function delete-root deletes the root node (with the smallest priority) from the treap.

Example:

> (root (delete-root (treap/priority symbol<?'(a. 4)'(b. 7)'(c. 2))))

- : Symbol

'a

Added in version 0.1 of package pfds.

top ← prev up next →