3 Heaps

7.7

3 Heaps

Following heap structures implement and provide the functions empty?, insert, find-min/max, delete-min/max, merge and sorted-list. All the heaps are polymorphic.

3.1 Binomial Heap

3.2 Skew Binomial Heap

3.3 Leftist Heap

3.4 Splay Heap

3.5 Pairing Heap

3.6 Lazy Pairing Heap

3.7 Bootstrapped Heap

3.1 Binomial Heap

(require pfds/heap/binomial)

package: pfds

Binomial Heaps are nothing but mergeable priority heaps. To avoid the confusion with FIFO queues, they are referred as heaps. Heaps are similar to the sortable collections but the difference is that comparison function is fixed when the heap is created. Binomial heaps are a binary representation with heap-ordered, binomial trees. A tree is heap-ordered if it maintains min-heap or max-heap property. Provides worst case running time of O(log(n)) for the operations insert, find-min/max, delete-min/max and merge.

syntax
(Heap A)

A binomial heap of type A.

procedure
(heap comp a ...) → (Heap A)
comp : (A A -> Boolean)
a : A

Function heap creates a Binomial Heap with the given inputs.

Example:

> (heap < 1 2 3 4 5 6)
- : (Heap Positive-Byte)
#<Heap>

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

procedure
(empty? heap) → Boolean
heap : (Heap A)

Function empty? checks if the given binomial heap is empty or not.

Examples:

> (empty? (heap < 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (heap <))
- : Boolean
#t

procedure
(insert a heap ...) → (Heap A)
a : A
heap : (Heap A)

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

Example:

> (insert 10 (heap < 1 2 3))
- : (Heap Positive-Byte)
#<Heap>

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

procedure
(find-min/max heap) → A
heap : (Heap A)

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

Examples:

> (find-min/max (heap < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (find-min/max (heap > 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
6
> (find-min/max (heap <))
find-min/max: given heap is empty

procedure
(delete-min/max heap) → (Heap A)
heap : (Heap A)

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

Examples:

> (delete-min/max (heap < 1 2 3 4 5 6))
- : (Heap Positive-Byte)
#<Heap>
> (delete-min/max (heap > 1 2 3 4 5 6))
- : (Heap Positive-Byte)
#<Heap>
> (delete-min/max (heap <))
delete-min/max: given heap is empty

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

procedure
(merge bheap1 bheap2) → (Heap A)
bheap1 : (Heap A)
bheap2 : (Heap A)

Function merge takes two binomial heaps and returns a merged binomial heap. Uses the comparison function of the first heap for merging and the same function becomes the comparison function for the merged heap.

If the comparison functions do not have the same properties, merged heap might lose its heap-order.

Examples:

> (define bheap1 (heap < 1 2 3 4 5 6))
> (define bheap2 (heap (λ: ([a : Integer]
                            [b : Integer])
                           (< a b))
                       10 20 30 40 50 60))
> (merge bheap1 bheap2)
eval:15:0: Type Checker: Polymorphic function `merge' could
not be applied to arguments:
Argument 1:
  Expected: (Heap A)
  Given:    (Heap Positive-Byte)
Argument 2:
  Expected: (Heap A)
  Given:    (Heap Integer)
  in: bheap2

In the above example, (merge bheap1 bheap2), merges the heaps and < will become the comparison function for the merged heap.

procedure
(sorted-list heap) → (Listof A)
heap : (Heap A)

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

Examples:

> (sorted-list (heap > 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(6 5 4 3 2 1)
> (sorted-list (heap < 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(1 2 3 4 5 6)

procedure
(map comparer func hep1 hep2 ...) → (Heap A)
  comparer : (C C -> Boolean)
  func : (A B ... B -> C)
  hep1 : (Heap A)
  hep2 : (Heap B)

Function map is similar to map for lists.

Examples:

> (sorted-list (map < add1 (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (sorted-list (map < * (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

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

procedure
(filter func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

Function filter is similar to filter.

Examples:

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

procedure
(remove func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

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

Examples:

> (sorted-list (remove (λ: ([x : Integer]) (> x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (sorted-list (remove (λ: ([x : Integer]) (< x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (sorted-list (remove (λ: ([x : Integer]) (<= x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function andmap is similar to andmap.

Examples:

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

procedure
(ormap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function ormap is similar to ormap.

Examples:

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

procedure
(build-heap size func comp) → (Heap A)
  size : Natural
  func : (Natural -> A)
  comp : (A A -> Boolean)

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

Examples:

> (sorted-list (build-heap 5 (λ:([x : Integer]) (add1 x)) <))
- : (Listof Integer)
'(1 2 3 4 5)
> (sorted-list (build-heap 5 (λ:([x : Integer]) (* x x)) <))
- : (Listof Integer)
'(0 1 4 9 16)

3.2 Skew Binomial Heap

(require pfds/heap/skew-binomial)

package: pfds

Skew Binomial Heaps are Binomial Heaps with hybrid numerical representation for heaps based on both skew binary numbers. Skew binary number representation is used since incrementing a skew binary number is quick and simple. Provides worst case running time of O(log(n)) for the operations find-min/max, delete-min/max and merge. And worst case running time of O(1) for the insert operation.

syntax
(Heap A)

A skew binomial heap of type A.

procedure
(heap comp a ...) → (Heap A)
comp : (A A -> Boolean)
a : A

Function heap creates a Skew Binomial Heap with the given inputs.

Example:

> (heap < 1 2 3 4 5 6)
- : (Heap Positive-Byte)
#<Heap>

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

procedure
(empty? heap) → Boolean
heap : (Heap A)

Function empty? checks if the given binomial heap is empty or not.

Examples:

> (empty? (heap < 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (heap <))
- : Boolean
#t

procedure
(insert a heap ...) → (Heap A)
a : A
heap : (Heap A)

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

Example:

> (insert 10 (heap < 1 2 3 4 5 6))
- : (Heap Positive-Byte)
#<Heap>

In the above example, insert adds the element 10 to (heap < 1 2 3 4 5 6).

procedure
(find-min/max heap) → A
heap : (Heap A)

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

Examples:

> (find-min/max (heap < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (find-min/max (heap > 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
6
> (find-min/max (heap <))
find-min/max: given heap is empty

procedure
(delete-min/max heap) → (Heap A)
heap : (Heap A)

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

Examples:

> (delete-min/max (heap < 1 2 3 4 5 6))
- : (Heap Positive-Byte)
#<Heap>
> (delete-min/max (heap > 1 2 3 4 5 6))
- : (Heap Positive-Byte)
#<Heap>
> (delete-min/max (heap <))
delete-min/max: given heap is empty

In the above example, (delete-min/max (heap < 1 2 3 4 5 6)) deletes 1 and returns (delete-min/max (heap < 2 3 4 5 6)). And (delete-min/max (heap > 1 2 3 4 5 6)) deletes 6 and returns (delete-min/max (heap < 1 2 3 4 5)).

procedure
(merge bheap1 bheap2) → (Heap A)
bheap1 : (Heap A)
bheap2 : (Heap A)

Function merge takes two binomial heaps and returns a merged binomial heap. Uses the comparison function in the first heap for merging and the same function becomes the comparison function for the merged heap.

If the comparison functions do not have the same properties, merged heap might lose its heap-order.

Examples:

> (define bheap1 (heap < 1 2 3 4 5 6))
> (define bheap2 (heap (λ: ([a : Integer]
                                    [b : Integer])
                                   (< a b))
                               10 20 30 40 50 60))
> (merge bheap1 bheap2)
eval:15:0: Type Checker: Polymorphic function `merge' could
not be applied to arguments:
Argument 1:
  Expected: (Heap A)
  Given:    (Heap Positive-Byte)
Argument 2:
  Expected: (Heap A)
  Given:    (Heap Integer)
  in: bheap2

In the above example, (merge bheap1 bheap2), merges the heaps and < will become the comparison function for the merged heap.

procedure
(sorted-list heap) → (Listof A)
heap : (Heap A)

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

Examples:

> (sorted-list (heap > 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(6 5 4 3 2 1)
> (sorted-list (heap < 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(1 2 3 4 5 6)

procedure
(map comparer func hep1 hep2 ...) → (Heap A)
  comparer : (C C -> Boolean)
  func : (A B ... B -> C)
  hep1 : (Heap A)
  hep2 : (Heap B)

Function map is similar to map for lists.

Examples:

> (sorted-list (map < add1 (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (sorted-list (map < * (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

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

procedure
(filter func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

Function filter is similar to filter.

Examples:

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

procedure
(remove func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

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

Examples:

> (sorted-list (remove (λ: ([x : Integer]) (> x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (sorted-list (remove (λ: ([x : Integer]) (< x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (sorted-list (remove (λ: ([x : Integer]) (<= x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function andmap is similar to andmap.

Examples:

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

procedure
(ormap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function ormap is similar to ormap.

Examples:

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

procedure
(build-heap size func comp) → (Heap A)
  size : Natural
  func : (Natural -> A)
  comp : (A A -> Boolean)

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

Examples:

> (sorted-list (build-heap 5 (λ:([x : Integer]) (add1 x)) <))
- : (Listof Integer)
'(1 2 3 4 5)
> (sorted-list (build-heap 5 (λ:([x : Integer]) (* x x)) <))
- : (Listof Integer)
'(0 1 4 9 16)

3.3 Leftist Heap

(require pfds/heap/leftist)

package: pfds

Leftist heaps are heap-ordered binary trees that satisfy the leftist property: the rank of any left child is at least as large as the rank of its right sibling. The rank of a node is defined to be the length of its right spine (i.e., the rightmost path from the node in question to an empty node). A simple consequence of the leftist property is that the right spine of any node is always the shortest path to an empty node.

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

syntax
(Heap A)

A leftist heap of type A.

procedure
(heap comp a ...) → (Heap A)
comp : (A A -> Boolean)
a : A

Function heap creates a Leftist Heap with the given inputs.

Example:

> (heap < 1 2 3 4 5 6)
- : (LeftistHeap Positive-Byte)
#<LeftistHeap>

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

procedure
(empty? heap) → Boolean
heap : (Heap A)

Function empty? checks if the given leftist heap is empty or not.

Examples:

> (empty? (heap < 1 2 3 4 5 6))
- : False
#f
> (empty? empty)
- : Boolean [more precisely: True]
#t

procedure
(insert a heap ...) → (Heap A)
a : A
heap : (Heap A)

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

Example:

> (insert 10 (heap < 1 2 3 4 5 6))
- : (LeftistHeap Positive-Byte)
#<LeftistHeap>

In the above example, insert adds the element 10 to the heap (heap < 1 2 3 4 5 6).

procedure
(find-min/max heap) → A
heap : (Heap A)

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

Examples:

> (find-min/max (heap < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (find-min/max (heap > 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
6
> (find-min/max (heap <))
find-min/max: given heap is empty

In the above example, (find-min/max lheap), returns the smallest element in lheap which happens to be 1.

procedure
(delete-min/max heap) → (Heap A)
heap : (Heap A)

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

Examples:

> (delete-min/max (heap < 1 2 3 4 5 6))
- : (LeftistHeap Positive-Byte)
#<LeftistHeap>
> (delete-min/max (heap > 1 2 3 4 5 6))
- : (LeftistHeap Positive-Byte)
#<LeftistHeap>
> (delete-min/max (heap <))
delete-min/max: given heap is empty

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

procedure
(merge lheap1 lheap2) → (Heap A)
lheap1 : (Heap A)
lheap2 : (Heap A)

Function merge takes two leftist heaps and returns a merged leftist heap. Uses the comparison function in the first heap for merging and the same function becomes the comparison function for the merged heap.

If the comparison functions do not have the same properties, merged heap might lose its heap-order.

Examples:

> (define lheap1 (heap < 1 2 3 4 5 6))
> (define lheap2 (heap (λ: ([a : Integer]
                                   [b : Integer])
                                  (< a b))
                              10 20 30 40 50 60))
> (merge lheap1 lheap2)
eval:15:0: Type Checker: Polymorphic function `merge' could
not be applied to arguments:
Argument 1:
  Expected: (LeftistHeap A)
  Given:    (LeftistHeap Positive-Byte)
Argument 2:
  Expected: (LeftistHeap A)
  Given:    (LeftistHeap Integer)
  in: lheap2

In the above example, (merge lheap1 lheap2), merges the heaps and < will become the comparison function for the merged heap.

procedure
(sorted-list heap) → (Listof A)
heap : (Heap A)

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

Examples:

> (sorted-list (heap > 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(6 5 4 3 2 1)
> (sorted-list (heap < 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(1 2 3 4 5 6)

procedure
(map comparer func hep1 hep2 ...) → (Heap A)
  comparer : (C C -> Boolean)
  func : (A B ... B -> C)
  hep1 : (Heap A)
  hep2 : (Heap B)

Function map is similar to map for lists.

Examples:

> (sorted-list (map < add1 (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (sorted-list (map < * (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

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

procedure
(filter func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

Function filter is similar to filter.

Examples:

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

procedure
(remove func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

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

Examples:

> (sorted-list (remove (λ: ([x : Integer]) (> x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (sorted-list (remove (λ: ([x : Integer]) (< x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (sorted-list (remove (λ: ([x : Integer]) (<= x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function andmap is similar to andmap.

Examples:

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

procedure
(ormap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function ormap is similar to ormap.

Examples:

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

procedure
(build-heap size func comp) → (Heap A)
  size : Natural
  func : (Natural -> A)
  comp : (A A -> Boolean)

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

Examples:

> (sorted-list (build-heap 5 (λ:([x : Integer]) (add1 x)) <))
- : (Listof Integer)
'(1 2 3 4 5)
> (sorted-list (build-heap 5 (λ:([x : Integer]) (* x x)) <))
- : (Listof Integer)
'(0 1 4 9 16)

3.4 Splay Heap

(require pfds/heap/splay)

package: pfds

Splay Heaps are very similar to balanced binary search trees. The difference between the two lies in the fact that Splay Heaps do not maintain any explicit balance information. Instead every operation restructures the tree with some simple transformations that increase the balance of the tree. Because of the restructuring on every operation, the worst case running time of all the operations is O(n). But it can be easily shown that the amortized running time of is O(log(n)) for the all the main operations insert, find-min/max, delete-min/max and merge.

syntax
(Heap A)

A splay heap of type A.

procedure
(heap comp a ...) → (Heap A)
comp : (A A -> Boolean)
a : A

Function heap creates a Splay Heap with the given inputs.

Example:

> (heap < 1 2 3 4 5 6)
- : (Heap Positive-Byte)
#<Heap>

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

procedure
(empty? heap) → Boolean
heap : (Heap A)

Function empty? checks if the given splay heap is empty or not.

Examples:

> (empty? (heap < 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (heap <))
- : Boolean
#t

procedure
(insert a heap ...) → (Heap A)
a : A
heap : (Heap A)

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

Example:

> (insert 10 (heap < 1 2 3 4 5 6))
- : (Heap Positive-Byte)
#<Heap>

In the above example, (insert 10 (heap < 1 2 3 4 5 6)) adds 10 to the heap (heap < 1 2 3 4 5 6).

procedure
(find-min/max heap) → A
heap : (Heap A)

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

Examples:

> (find-min/max (heap < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (find-min/max (heap > 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
6
> (find-min/max (heap <))
find-min/max: given heap is empty

procedure
(delete-min/max heap) → (Heap A)
heap : (Heap A)

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

Examples:

> (delete-min/max (heap < 1 2 3 4 5 6))
- : (Heap Positive-Byte)
#<Heap>
> (delete-min/max (heap > 1 2 3 4 5 6))
- : (Heap Positive-Byte)
#<Heap>
> (delete-min/max (heap >))
delete-min/max: given heap is empty

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

procedure
(merge sheap1 sheap2) → (Heap A)
sheap1 : (Heap A)
sheap2 : (Heap A)

Function merge takes two splay heaps and returns a merged splay heap. Uses the comparison function in the first heap for merging and the same function becomes the comparison function for the merged heap.

If the comparison functions do not have the same properties, merged heap might lose its heap-order.

Examples:

> (define sheap1 (heap < 1 2 3 4 5 6))
> (define sheap2 (heap (λ: ([a : Integer]
                                 [b : Integer])
                                (< a b))
                            10 20 30 40 50 60))
> (merge sheap1 sheap2)
eval:15:0: Type Checker: Polymorphic function `merge' could
not be applied to arguments:
Argument 1:
  Expected: (Heap A)
  Given:    (Heap Positive-Byte)
Argument 2:
  Expected: (Heap A)
  Given:    (Heap Integer)
  in: sheap2

In the above example, (merge sheap1 sheap2), merges the heaps and < will become the comparison function for the merged heap.

procedure
(sorted-list heap) → (Listof A)
heap : (Heap A)

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

Examples:

> (sorted-list (heap > 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(6 5 4 3 2 1)
> (sorted-list (heap < 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(1 2 3 4 5 6)
> (sorted-list (heap >))
- : (Listof Nothing)
'()

procedure
(map comparer func hep1 hep2 ...) → (Heap A)
  comparer : (C C -> Boolean)
  func : (A B ... B -> C)
  hep1 : (Heap A)
  hep2 : (Heap B)

Function map is similar to map for lists.

Examples:

> (sorted-list (map < add1 (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (sorted-list (map < * (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

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

procedure
(filter func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

Function filter is similar to filter.

Examples:

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

procedure
(remove func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

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

Examples:

> (sorted-list (remove (λ: ([x : Integer]) (> x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (sorted-list (remove (λ: ([x : Integer]) (< x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (sorted-list (remove (λ: ([x : Integer]) (<= x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function andmap is similar to andmap.

Examples:

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

procedure
(ormap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function ormap is similar to ormap.

Examples:

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

procedure
(build-heap size func comp) → (Heap A)
  size : Natural
  func : (Natural -> A)
  comp : (A A -> Boolean)

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

Examples:

> (sorted-list (build-heap 5 (λ:([x : Integer]) (add1 x)) <))
- : (Listof Integer)
'(1 2 3 4 5)
> (sorted-list (build-heap 5 (λ:([x : Integer]) (* x x)) <))
- : (Listof Integer)
'(0 1 4 9 16)

3.5 Pairing Heap

(require pfds/heap/pairing)

package: pfds

Pairing Heap is a type of heap which has a very simple implementation and has extremely good performance in practice. Pairing Heaps provide a worst case running time of O(1) for the operations insert find-min/max merge. And delete-min/max has a amortized running time of O(log(n)).

syntax
(Heap A)

A pairing heap of type A.

procedure
(heap comp a ...) → (Heap A)
comp : (A A -> Boolean)
a : A

Function heap creates a Pairing Heap with the given inputs.

Example:

> (heap < 1 2 3 4 5 6)
- : (PairingHeap Positive-Byte)
#<PairingHeap>

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

procedure
(empty? heap) → Boolean
heap : (Heap A)

Function empty? checks if the given pairing heap is empty or not.

Examples:

> (empty? (heap < 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (heap <))
- : Boolean
#t

procedure
(insert a heap ...) → (Heap A)
a : A
heap : (Heap A)

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

Example:

> (insert 10 (heap < 1 2 3 4 5 6))
- : (PairingHeap Positive-Byte)
#<PairingHeap>

In the above example, (insert 10 (heap < 1 2 3 4 5 6)) adds the element 10 to (heap < 1 2 3 4 5 6).

procedure
(find-min/max heap) → A
heap : (Heap A)

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

Examples:

> (find-min/max (heap < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (find-min/max (heap > 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
6
> (find-min/max (heap >))
find-min/max: given heap is empty

procedure
(delete-min/max heap) → (Heap A)
heap : (Heap A)

Function delete-min/max takes a pairing heap and returns the same heap with out the min or max element in the given heap. The element removed from the heap is max or min depends on the comparison function of the heap. For

Examples:

> (delete-min/max (heap < 1 2 3 4 5 6))
- : (PairingHeap Positive-Byte)
#<PairingHeap>
> (delete-min/max (heap > 1 2 3 4 5 6))
- : (PairingHeap Positive-Byte)
#<PairingHeap>
> (delete-min/max (heap <))
delete-min/max: given heap is empty

In the above example, (delete-min/max (heap < 1 2 3 4 5 6)), deletes the smallest element 1 in the heap (heap < 1 2 3 4 5 6). And (delete-min/max (heap > 1 2 3 4 5 6)) deletes the largest element which is 6.

procedure
(merge pheap1 pheap2) → (Heap A)
pheap1 : (Heap A)
pheap2 : (Heap A)

Function merge takes two pairing heaps and returns a merged pairing heap. Uses the comparison function in the first heap for merging and the same function becomes the comparison function for the merged heap.

If the comparison functions do not have the same properties, merged heap might lose its heap-order.

Examples:

> (define pheap1 (heap < 1 2 3 4 5 6))
> (define pheap2 (heap (λ: ([a : Integer]
                                   [b : Integer])
                                  (< a b))
                              10 20 30 40 50 60))
> (merge pheap1 pheap2)
eval:15:0: Type Checker: Polymorphic function `merge' could
not be applied to arguments:
Argument 1:
  Expected: (PairingHeap A)
  Given:    (PairingHeap Positive-Byte)
Argument 2:
  Expected: (PairingHeap A)
  Given:    (PairingHeap Integer)
  in: pheap2

In the above example, (merge pheap1 pheap2), merges the heaps and < will become the comparison function for the merged heap.

procedure
(sorted-list heap) → (Listof A)
heap : (Heap A)

Function sorted-list takes a pairing heap and returns a list which is sorted according to the comparison function of the heap. For

Examples:

> (sorted-list (heap > 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(6 5 4 3 2 1)
> (sorted-list (heap < 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(1 2 3 4 5 6)

procedure
(map comparer func hep1 hep2 ...) → (Heap A)
  comparer : (C C -> Boolean)
  func : (A B ... B -> C)
  hep1 : (Heap A)
  hep2 : (Heap B)

Function map is similar to map for lists.

Examples:

> (sorted-list (map < add1 (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (sorted-list (map < * (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

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

procedure
(filter func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

Function filter is similar to filter.

Examples:

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

procedure
(remove func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

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

Examples:

> (sorted-list (remove (λ: ([x : Integer]) (> x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (sorted-list (remove (λ: ([x : Integer]) (< x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (sorted-list (remove (λ: ([x : Integer]) (<= x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function andmap is similar to andmap.

Examples:

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

procedure
(ormap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function ormap is similar to ormap.

Examples:

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

procedure
(build-heap size func comp) → (Heap A)
  size : Natural
  func : (Natural -> A)
  comp : (A A -> Boolean)

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

Examples:

> (sorted-list (build-heap 5 (λ:([x : Integer]) (add1 x)) <))
- : (Listof Integer)
'(1 2 3 4 5)
> (sorted-list (build-heap 5 (λ:([x : Integer]) (* x x)) <))
- : (Listof Integer)
'(0 1 4 9 16)

3.6 Lazy Pairing Heap

(require pfds/heap/lazy-pairing)

package: pfds

Lazy Pairing Heap is very similar to Pairing Heap. The only difference between the two is, as the name suggests, Lazy Pairing Heap is lazy in nature.

syntax
(Heap A)

A lazy pairing heap of type A.

procedure
(heap comp a ...) → (Heap A)
comp : (A A -> Boolean)
a : A

Function heap creates a Lazy Pairing Heap with the given inputs.

Example:

> (heap < 1 2 3 4 5 6)
- : (PairingHeap Positive-Byte)
#<PairingHeap>

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

procedure
(empty? heap) → Boolean
heap : (Heap A)

Function empty? checks if the given lazy pairing heap is empty or not.

Examples:

> (empty? (heap < 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (heap <))
- : Boolean
#t

procedure
(insert a heap ...) → (Heap A)
a : A
heap : (Heap A)

Function insert takes an element and a lazy pairing heap and inserts the given element into the lazy pairing heap.

Example:

> (insert 10 (heap < 1 2 3 4 5 6))
- : (PairingHeap Positive-Byte)
#<PairingHeap>

In the above example, (insert 10 (heap < 1 2 3 4 5 6)) adds the element 10 to the heap (heap < 1 2 3 4 5 6).

procedure
(find-min/max heap) → A
heap : (Heap A)

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

Examples:

> (find-min/max (heap < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (find-min/max (heap > 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
6
> (find-min/max (heap <))
find-min/max: given heap is empty

procedure
(delete-min/max heap) → (Heap A)
heap : (Heap A)

Function delete-min/max takes a lazy pairing heap and returns the same heap with out the min or max element in the given heap. The element removed from the heap is max or min depends on the comparison function of the heap.

Examples:

> (delete-min/max (heap < 1 2 3 4 5 6))
- : (PairingHeap Positive-Byte)
#<PairingHeap>
> (delete-min/max (heap > 1 2 3 4 5 6))
- : (PairingHeap Positive-Byte)
#<PairingHeap>
> (delete-min/max (heap >))
delete-min/max: given heap is empty

procedure
(merge pheap1 pheap2) → (Heap A)
pheap1 : (Heap A)
pheap2 : (Heap A)

Function merge takes two lazy pairing heaps and returns a merged lazy pairing heap. Uses the comparison function in the first heap for merging and the same function becomes the comparison function for the merged heap.

If the comparison functions do not have the same properties, merged heap might lose its heap-order.

Examples:

> (define pheap1 (heap < 1 2 3 4 5 6))
> (define pheap2 (heap (λ: ([a : Integer]
                                   [b : Integer])
                                  (< a b))
                              10 20 30 40 50 60))
> (merge pheap1 pheap2)
eval:15:0: Type Checker: Polymorphic function `merge' could
not be applied to arguments:
Argument 1:
  Expected: (PairingHeap A)
  Given:    (PairingHeap Positive-Byte)
Argument 2:
  Expected: (PairingHeap A)
  Given:    (PairingHeap Integer)
  in: pheap2

In the above example, (merge pheap1 pheap2), merges the heaps and < will become the comparison function for the merged heap.

procedure
(sorted-list heap) → (Listof A)
heap : (Heap A)

Function sorted-list takes a lazy pairing heap and returns a list which is sorted according to the comparison function of the heap.

Examples:

> (sorted-list (heap > 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(6 5 4 3 2 1)
> (sorted-list (heap < 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(1 2 3 4 5 6)

procedure
(map comparer func hep1 hep2 ...) → (Heap A)
  comparer : (C C -> Boolean)
  func : (A B ... B -> C)
  hep1 : (Heap A)
  hep2 : (Heap B)

Function map is similar to map for lists.

Examples:

> (sorted-list (map < add1 (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (sorted-list (map < * (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

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

procedure
(filter func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

Function filter is similar to filter.

Examples:

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

procedure
(remove func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

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

Examples:

> (sorted-list (remove (λ: ([x : Integer]) (> x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (sorted-list (remove (λ: ([x : Integer]) (< x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (sorted-list (remove (λ: ([x : Integer]) (<= x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function andmap is similar to andmap.

Examples:

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

procedure
(ormap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function ormap is similar to ormap.

Examples:

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

procedure
(build-heap size func comp) → (Heap A)
  size : Natural
  func : (Natural -> A)
  comp : (A A -> Boolean)

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

Examples:

> (sorted-list (build-heap 5 (λ:([x : Integer]) (add1 x)) <))
- : (Listof Integer)
'(1 2 3 4 5)
> (sorted-list (build-heap 5 (λ:([x : Integer]) (* x x)) <))
- : (Listof Integer)
'(0 1 4 9 16)

3.7 Bootstrapped Heap

(require pfds/heap/bootstrapped)

package: pfds

Bootstrapped heaps are heaps with efficient merging. The bootstrapped heap is implemented with structural abstraction over a less efficient heap implementation to get a worst case running time of O(1) for the operations insert, find-min/max and merge and worst case running time of O(log(n)) for delete-min/max operation. This implementation abstracts over skew binomial heaps. For skew binomial heaps, see Skew Binomial Heap.

syntax
(Heap A)

A bootstrapped heap of type A.

procedure
(heap comp a ...) → (Heap A)
comp : (A A -> Boolean)
a : A

Function heap creates a Bootstrapped Heap with the given inputs.

Example:

> (heap < 1 2 3 4 5 6)
- : (BSHeap Positive-Byte)
#<BSHeap>

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

procedure
(empty? heap) → Boolean
heap : (Heap A)

Function empty? checks if the given bootstrapped heap is empty or not.

Examples:

> (empty? (heap < 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (heap <))
- : Boolean
#t

procedure
(insert a heap ...) → (Heap A)
a : A
heap : (Heap A)

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

Example:

> (insert 10 (heap < 1 2 3 4 5 6))
- : (BSHeap Positive-Byte)
#<BSHeap>

In the above example, insert adds the element 10 to the heap (heap < 1 2 3 4 5 6).

procedure
(find-min/max heap) → A
heap : (Heap A)

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

Examples:

> (find-min/max (heap < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (find-min/max (heap > 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
6
> (find-min/max (heap <))
find-min/max: given heap is empty

procedure
(delete-min/max heap) → (Heap A)
heap : (Heap A)

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

Examples:

> (delete-min/max (heap < 1 2 3 4 5 6))
- : (BSHeap Positive-Byte)
#<BSHeap>
> (delete-min/max (heap > 1 2 3 4 5 6))
- : (BSHeap Positive-Byte)
#<BSHeap>
> (delete-min/max (heap <))
delete-min/max: given heap is empty

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

procedure
(merge heap1 heap2) → (Heap A)
heap1 : (Heap A)
heap2 : (Heap A)

Function merge takes two bootstrapped heaps and returns a merged bootstrapped heap. Uses the comparison function in the first heap for merging and the same function becomes the comparison function for the merged heap.

If the comparison functions do not have the same properties, merged heap might lose its heap-order.

Examples:

> (define bheap1 (heap < 1 2 3 4 5 6))
> (define bheap2 (heap (λ: ([a : Integer]
                                         [b : Integer])
                                        (< a b))
                                    10 20 30 40 50 60))
> (merge bheap1 bheap2)
eval:15:0: Type Checker: Polymorphic function `merge' could
not be applied to arguments:
Argument 1:
  Expected: (BSHeap A)
  Given:    (BSHeap Positive-Byte)
Argument 2:
  Expected: (BSHeap A)
  Given:    (BSHeap Integer)
  in: bheap2

In the above example, (merge bheap1 bheap2), merges the heaps and < will become the comparison function for the merged heap.

procedure
(sorted-list heap) → (Listof A)
heap : (Heap A)

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

Examples:

> (sorted-list (heap > 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(6 5 4 3 2 1)
> (sorted-list (heap < 1 2 3 4 5 6))
- : (Listof Positive-Byte)
'(1 2 3 4 5 6)

In the above example, (sorted-list bheap), returns (6 5 4 3 2 1).

procedure
(map comparer func hep1 hep2 ...) → (Heap A)
  comparer : (C C -> Boolean)
  func : (A B ... B -> C)
  hep1 : (Heap A)
  hep2 : (Heap B)

Function map is similar to map for lists.

Examples:

> (sorted-list (map < add1 (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (sorted-list (map < * (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

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

procedure
(filter func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

Function filter is similar to filter.

Examples:

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

procedure
(remove func hep) → (Heap A)
func : (A -> Boolean)
hep : (Heap A)

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

Examples:

> (sorted-list (remove (λ: ([x : Integer]) (> x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (sorted-list (remove (λ: ([x : Integer]) (< x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (sorted-list (remove (λ: ([x : Integer]) (<= x 5))
                      (heap < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function andmap is similar to andmap.

Examples:

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

procedure
(ormap func heap1 heap2 ...) → Boolean
  func : (A B ... B -> Boolean)
  heap1 : (Heap A)
  heap2 : (Heap B)

Function ormap is similar to ormap.

Examples:

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

procedure
(build-heap size func comp) → (Heap A)
  size : Natural
  func : (Natural -> A)
  comp : (A A -> Boolean)

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

Examples:

> (sorted-list (build-heap 5 (λ:([x : Integer]) (add1 x)) <))
- : (Listof Integer)
'(1 2 3 4 5)
> (sorted-list (build-heap 5 (λ:([x : Integer]) (* x x)) <))
- : (Listof Integer)
'(0 1 4 9 16)

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

3.1	Binomial Heap
3.2	Skew Binomial Heap
3.3	Leftist Heap
3.4	Splay Heap
3.5	Pairing Heap
3.6	Lazy Pairing Heap
3.7	Bootstrapped Heap