9 Treap

7.7

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. Elements are assigned a random priority between from 0 to 1.

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
(contains? a treap) → 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 < 1 2 3 4 5 6))
- : Boolean
#t
> (contains? 4 (treap < 1 2 3 5 6 7))
- : Boolean
#f

Added in version 0.1 of package pfds.

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 with a random priority between 0 and 1.

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

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)
'(6 2 4 3 5 7)
> (treap->list (map < * (treap < 1 2 3 4 5 6) (treap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(4 1 15 36 16 15)

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)
'(4 2 1 3)
> (treap->list (filter (λ: ([x : Integer]) (<= x 5)) trp))
- : (Listof Positive-Byte)
'(4 1 2 3 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)
'(5 6)
> (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)
'(3 2 1 4 5)
> (treap->list (build-treap 5 (λ:([x : Integer]) (* x x)) <))
- : (Listof Integer)
'(0 9 4 1 16)

9.1 Priorities

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

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))
- : (Treap Positive-Byte)
#<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 a priority treap) → (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 < 1 2 3))
- : (Treap Positive-Byte)
#<Treap>
> (root (insert/priority 10 -4 (treap < 1 2 3)))
- : Integer [more precisely: Positive-Byte]
10
> (root (insert/priority 10 4 (treap < 1 2 3)))
- : Integer [more precisely: Positive-Byte]
2

In the above examples, insert/priority adds the element 10 to (treap < 1 2 3) 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 < 1 2 3))
- : 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 →

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