## The Pairing Heap Egg

### Introduction

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))) (letloop((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

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