You can edit this page using wiki syntax for markup.

Article contents:== Outdated egg! This is an egg for CHICKEN 3, the unsupported old release. You're almost certainly looking for [[/eggref/4/pairing-heap|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 [[https://wiki.call-cc.org/chicken-projects/egg-index-4.html|egg index]]. Otherwise, please consider porting this egg to the current version of CHICKEN. [[tags:eggs]] == The Pairing Heap Egg [[toc:]] === 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: <enscript highlight=scheme> (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)) </enscript> === Authors [[mailto:farr@mit.edu|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 [[http://srfi.schemers.org/srfi-67/|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 <enscript highlight=scheme> (define (fixnum-compare n1 n2) (cond ((fx< n1 n2) -1) ((fx= n1 n2) 0) (else 1))) </enscript> ==== 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 <enscript highlight=scheme> (define (pairing-heap->list h) (pairing-heap-fold cons '() h)) </enscript> [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. Description of your changes:

I would like to authenticate

Spam control

What do you get when you subtract 8 from 8?