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 and have the type (Heap A).

3.1 Binomial Heap

(require "binomialheap.ss")

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

3.2 Skew Binomial Heap

(require "skewbinomialheap.ss")

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

3.3 Leftist Heap

(require "leftistheaps.ss")

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

3.4 Splay Heap

(require "splayheap.ss")

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.

In the above example, the splay 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 10 (heap < 1 2 3 4 5 6)) adds 10 to the heap (heap < 1 2 3 4 5 6).

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.

In the above example, (merge sheap1 sheap2), 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