9 Treap

6.3.90.900

top ← prev up next →

9 Treap

package: pfds

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 comp a ...) → (Treap A)
comp : (A A -> Boolean)
a : A

Function treap creates a Treap with the given inputs.

Example:

> (treap < 1 2 3 4 5 6)
- : (Treap Positive-Byte)
#<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 < 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (treap <))
- : Boolean
#t

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

Function insert takes an element and a treap and inserts the given element into the treap.

Example:

> (insert 10 (treap < 1 2 3))
- : (Treap Positive-Byte)
#<Treap>

In the above example, insert adds the element 10 to (treap < 1 2 3).

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 < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (find-min/max (treap > 1 2 3 4 5 6))
- : 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 < 1 2 3 4 5 6))
- : (Treap Positive-Byte)
#<Treap>
> (delete-min/max (treap > 1 2 3 4 5 6))
- : (Treap Positive-Byte)
#<Treap>
> (delete-min/max (treap <))
delete-min/max: given treap is empty

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

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

Function delete deletes the given element from the given treap.

Examples:

> (delete 6 (treap < 1 2 3 4 5 6))
- : (Treap Positive-Byte)
#<Treap>
> (delete 3 (treap > 1 2 3 4 5 6))
- : (Treap Positive-Byte)
#<Treap>
> (delete 10 (treap <))
eval:15:0: Type Checker: Polymorphic function `delete' could
not be applied to arguments:
Argument 1:
  Expected: A
  Given:    Positive-Byte
Argument 2:
  Expected: (Treap A)
  Given:    (Treap Nothing)
  in: <

In the above example, (delete 6 (treap < 1 2 3 4 5 6)), deletes the 6 returns (treap < 1 2 3 4 5). And (delete 3 (treap > 1 2 3 4 5 6)) returns (treap > 1 2 4 5 6).

procedure
(treap->list treap) → (Listof A)
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 > 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(4 6 5 3 2 1)
> (treap->list (treap < 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(6 2 1 5 4 3)

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

Function map is similar to map for lists.

Examples:

> (treap->list (map < add1 (treap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(7 2 3 6 4 5)
> (treap->list (map < * (treap < 1 2 3 4 5 6) (treap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(12 1 4 25 24 18)

procedure
(fold func init treap1 treap2 ...) → C
  func : (C A B ... 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 < 1 2 3 4 5 6))
- : Integer [more precisely: Nonnegative-Integer]
21
> (fold * 1 (treap < 1 2 3 4 5 6) (treap < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Integer]
518400

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

Function filter is similar to filter.

Examples:

> (define trp (treap < 1 2 3 4 5 6))
> (treap->list (filter (λ: ([x : Integer]) (> x 5)) trp))
- : (Listof Positive-Byte)
'(6)
> (treap->list (filter (λ: ([x : Integer]) (< x 5)) trp))
- : (Listof Positive-Byte)
'(2 1 3 4)
> (treap->list (filter (λ: ([x : Integer]) (<= x 5)) trp))
- : (Listof Positive-Byte)
'(4 3 2 1 5)

procedure
(remove func treap) → (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]) (> x 5))
                       (treap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(4 2 1 3 5)
> (treap->list (remove (λ: ([x : Integer]) (< x 5))
                       (treap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6 5)
> (treap->list (remove (λ: ([x : Integer]) (<= x 5))
                       (treap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

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

Function andmap is similar to andmap.

Examples:

> (andmap even? (treap < 1 2 3 4 5 6))
- : Boolean
#f
> (andmap odd? (treap < 1 2 3 4 5 6))
- : Boolean
#f
> (andmap positive? (treap < 1 2 3 4 5 6))
- : Boolean
#t
> (andmap negative? (treap < -1 -2))
- : Boolean
#t

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

Function ormap is similar to ormap.

Examples:

> (ormap even? (treap < 1 2 3 4 5 6))
- : Boolean
#t
> (ormap odd? (treap < 1 2 3 4 5 6))
- : Boolean
#t
> (ormap positive? (treap < -1 -2 3 4 -5 6))
- : Boolean
#t
> (ormap negative? (treap < 1 -2))
- : Boolean
#t

procedure
(build-treap size func comp) → (Treap A)
  size : Natural
  func : (Natural -> A)
  comp : (A A -> 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]) (add1 x)) <))
- : (Listof Integer)
'(5 2 1 4 3)
> (treap->list (build-treap 5 (λ:([x : Integer]) (* x x)) <))
- : (Listof Integer)
'(16 0 4 1 9)

top ← prev up next →

1	Queues
2	Deques
3	Heaps
4	Random Access Lists
5	VList
6	Streams
7	Red-Black Trees
8	Tries
9	Treap