Outdated egg!

This is an egg for CHICKEN 3, the unsupported old release. You're almost certainly looking for the CHICKEN 4 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

eggs

The pairing-heap egg provides a heap datastructure which is persistent (operations on an existing heap do not modify it, but rather return a new heap which shares some structure with the old heap). The egg uses memoization and lazy evaluation (via force and delay) to ensure that the following operations complete within the bounds given below.

Examples

Sort a List

If the pairing-heap egg did not provide a pairing-heap-sort operation on lists, here is how you could code it:

(use srfi-1)
(use pairing-heap)

;; compare should take two objects and return -1, 0, or 1, depending
;; on whether they are <, =, >.
;;
;; We invert the comparison relation when making the heap to avoid
;; having to reverse the output list.
(define (ph-sort compare list)
  (let ((rev-compare (lambda (obj1 obj2) (fx* -1 (compare obj1 obj2)))))
    (let ((h (fold pairing-heap-insert (pairing-heap-empty rev-compare) list)))
      (let loop ((sorted-elts '())
                 (h h))
        (if (pairing-heap-empty? h)
            sorted-elts
            (loop (cons (pairing-heap-min h) sorted-elts)
                  (pairing-heap-remove-min h)))))))

;; Returns '(1 2 3 4 5 6 7 8 9 10)
(ph-sort (lambda (n1 n2) (cond ((< n1 n2) -1) ((= n1 n2) 0) (else 1)))
         '(10 9 5 4 6 7 8 2 3 1))

Authors

Will M. Farr

License

The pairing-heap egg is released under a BSD License.

Requirements

This egg requires only the base chicken system.

Procedures

A Note on Compare Procedures

The pairing-heap egg is compatible with SRFI-67, though it does not require any SRFI-67 code to be loaded at runtime or compile-time. This means that comparison procedures take two arguments, OBJ1 and OBJ2, and should return

-1 if OBJ1 < OBJ2
0 if OBJ1 = OBJ2
1 if OBJ1 > OBJ2

Thus, an appropriate fixnum-comparison procedure would be

(define (fixnum-compare n1 n2)
  (cond
   ((fx< n1 n2) -1)
   ((fx= n1 n2) 0)
   (else 1)))

Exported Procedures

The following procedures are provided by the pairing-heap egg. In the following, COMPARE is a comparison function as described in the last section, OBJ is a generic scheme object, H and Hi, where i is an integer, are pairing-heaps, and n refers to the number of elements in a heap:

[procedure] (pairing-heap? OBJ)

#f unless OBJ is a pairing heap.

[procedure] (pairing-heap-empty COMPARE)

Construct an empty heap which uses COMPARE to compare elements.

[procedure] (pairing-heap-empty? H)

#f unless the pairing-heap H is empty.

[procedure] (pairing-heap-min H)

Returns the smallest element in the heap H. Completes in O(1) time.

[procedure] (pairing-heap-insert OBJ H)

Returns a new heap which contains all elements of H in addition to OBJ. Completes in O(1) time.

[procedure] (pairing-heap-merge H1 H2)

Returns a new heap which contains all elements from H1 and all elements from H2. Completes in O(1) time.

[procedure] (pairing-heap-remove-min H)

Returns a new heap which contains all elements from H except the smallest. Can complete in O(n) time, but a sequence of pairing-heap-remove-min operations complete in averaged O(log(n)) time. (i.e. amortized log(n) bounds.)

[procedure] (pairing-heap-fold KONS KNIL H)

Applies the two-argument procedure KONS to the elements of H and an accumulation value in unspecified order. KNIL is the initial accumulation value, and the result of each KONS application is used for the next accumulation. If H is empty, KNIL is returned. The result of pairing-heap-fold is the result of the final KONS application. Completes in O(n) time. For example, one could define pairing-heap->list as

(define (pairing-heap->list h) (pairing-heap-fold cons '() h))

[procedure] (pairing-heap-sort COMPARE LIST-OR-VECTOR)

Returns a list or vector (depending on the type of LIST-OR-VECTOR) which contains all elements of LIST-OR-VECTOR, but in non-decreasing order. Completes in O(n*log(n)) time.

Version History

Version 1.0: Initial release.