source: project/wiki/pairing-heap @ 5798

Last change on this file since 5798 was 5798, checked in by wmfarr, 13 years ago

Changes applied for wmfarr (18.95.7.238) through svnwiki:

Fixed typo.

File size: 4.3 KB
Line 
1[[tags:eggs]]
2
3== The Pairing Heap Egg
4
5[[toc:]]
6
7=== Introduction
8
9The 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.
10
11=== Examples
12
13==== Sort a List
14
15If the pairing-heap egg did not provide a {{pairing-heap-sort}} operation on lists, here is how you could code it:
16
17<enscript highlight=scheme>
18(use srfi-1)
19(use pairing-heap)
20
21;; compare should take two objects and return -1, 0, or 1, depending
22;; on whether they are <, =, >.
23;;
24;; We invert the comparison relation when making the heap to avoid
25;; having to reverse the output list.
26(define (ph-sort compare list)
27  (let ((rev-compare (lambda (obj1 obj2) (fx* -1 (compare obj1 obj2)))))
28    (let ((h (fold pairing-heap-insert (pairing-heap-empty rev-compare) list)))
29      (let loop ((sorted-elts '())
30                 (h h))
31        (if (pairing-heap-empty? h)
32            sorted-elts
33            (loop (cons (pairing-heap-min h) sorted-elts)
34                  (pairing-heap-remove-min h)))))))
35
36;; Returns '(1 2 3 4 5 6 7 8 9 10)
37(ph-sort (lambda (n1 n2) (cond ((< n1 n2) -1) ((= n1 n2) 0) (else 1)))
38         '(10 9 5 4 6 7 8 2 3 1))
39</enscript>
40
41=== Authors
42
43[[mailto:farr@mit.edu|Will M. Farr]]
44
45=== License
46
47The pairing-heap egg is released under a BSD License.
48
49=== Requirements
50
51This egg requires only the base chicken system.
52
53=== Procedures
54
55==== A Note on Compare Procedures
56
57The 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
58
59* -1 if {{OBJ1 < OBJ2}}
60* 0 if {{OBJ1 = OBJ2}}
61* 1 if {{OBJ1 > OBJ2}}
62
63Thus, an appropriate fixnum-comparison procedure would be
64
65<enscript highlight=scheme>
66(define (fixnum-compare n1 n2)
67  (cond
68   ((fx< n1 n2) -1)
69   ((fx= n1 n2) 0)
70   (else 1)))
71</enscript>
72
73==== Exported Procedures
74
75The 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:
76
77 [procedure] (pairing-heap? OBJ)
78
79{{#f}} unless {{OBJ}} is a pairing heap.
80
81 [procedure] (pairing-heap-empty COMPARE)
82
83Construct an empty heap which uses {{COMPARE}} to compare elements.
84
85 [procedure] (pairing-heap-empty? H)
86
87{{#f}} unless the pairing-heap {{H}} is empty.
88
89 [procedure] (pairing-heap-min H)
90
91Returns the smallest element in the heap {{H}}.  Completes in O(1) time.
92
93 [procedure] (pairing-heap-insert OBJ H)
94
95Returns a new heap which contains all elements of {{H}} in addition to {{OBJ}}.  Completes in O(1) time.
96
97 [procedure] (pairing-heap-merge H1 H2)
98
99Returns a new heap which contains all elements from {{H1}} and all elements from {{H2}}.  Completes in O(1) time.
100
101 [procedure] (pairing-heap-remove-min H)
102
103Returns 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.)
104
105 [procedure] (pairing-heap-fold KONS KNIL H)
106
107Applies 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
108
109<enscript highlight=scheme>
110(define (pairing-heap->list h) (pairing-heap-fold cons '() h))
111</enscript>
112
113 [procedure] (pairing-heap-sort COMPARE LIST-OR-VECTOR)
114
115Returns 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.
116
117=== Version History
118
119; Version 1.0 : Initial release.
Note: See TracBrowser for help on using the repository browser.