[plt-scheme] Will it float? [Heaps Galore]

HEAPS GALORE
------------

I have for some time felt that a library of useful data structures is
needed. To get started I have written a little library of heaps.

The following is a little excerpt of the documentation:

   <http://www.scheme.dk/heaps-galore/doc-heap.txt>

The library and example files can be seen at

   <http://www.scheme.dk/heaps-galore/>


Will it float?
Is this anything?
Shall I bring in Grinder Girl?

/Jens Axel Søgaard



INTRODUCTION
------------

The heaps are implemented in a purely functional way. Inserting an
element in a heap will return a new heap containing the element and
all elements in the old heap *without* destroying the old heap.  The
heaps can thus be used *persistently* opposed to the normal
*ephemeral* way, where the old heap are destroyed. This implies that
the heaps are safe to use in multi threaded programs and web servlets.

The algorithms are carefully explained by Chris Okasaki in the
delightful book "Purely Functional Data Structures".

This library implements the following heap algorithms:

   - leftist heaps
   - binomial heaps
   - pairing-heaps
   - splay heaps
   - lazy binomial heaps
   - lazy pairing heaps
   - skew binomial heaps

Furthermore a bootstrapping functor is provided that can improve the
worst case times of find-min and merge to O(1) for certain heaps.

There is support for using heaps of different types of elements at the
same time.

EXAMPLE (Simple)
----------------

; A pairing heap of integers
 > (use-heap (instantiate-heap pairing-heap@ integers@))
 > (find-min (insert 42 (insert 3 empty)))
3

; A binomial heap of strings
 > (use-heap (instantiate-heap binomial-heap@ strings@) bsh)
 > (bsh:find-min (bsh:insert "foo" (bsh:insert "bar" (bsh:insert "baz" 
bsh:empty))))
"bar"

; A leftist heap of strings
 > (use-heap (instantiate-heap leftist-heap@ strings@) lsh)
 > (lsh:find-min (lsh:insert "foo" (lsh:insert "bar" (lsh:insert "baz" 
lsh:empty))))
"bar"