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

(require (planet krhari/pfds:1:5/binomialheap))

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.

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

Examples:

> (empty? (heap < 1 2 3 4 5 6))

- : Boolean

#f

> (empty? (heap <))

- : Boolean

#t

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

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.

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

Examples:

> (fold + 0 (heap < 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (fold * 1 (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400

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

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

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 (planet krhari/pfds:1:5/skewbinomialheap))

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.

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

Examples:

> (empty? (heap < 1 2 3 4 5 6))

- : Boolean

#f

> (empty? (heap <))

- : Boolean

#t

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

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)).

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)

- : (Heap Positive-Fixnum)

#<Heap>

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

Examples:

> (fold + 0 (heap < 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (fold * 1 (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400

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

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

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 (planet krhari/pfds:1:5/leftistheap))

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.

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

Examples:

> (empty? (heap < 1 2 3 4 5 6))

- : Boolean

#f

> (empty? empty)

- : Boolean

#t

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

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

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.

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)

- : (LeftistHeap Positive-Fixnum)

#<LeftistHeap>

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

Examples:

> (fold + 0 (heap < 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (fold * 1 (heap < 1 2 3 4 5 6) (heap < 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400