1 | [[tags:eggs]] |
---|
2 | |
---|
3 | == The Pairing Heap Egg |
---|
4 | |
---|
5 | [[toc:]] |
---|
6 | |
---|
7 | === Introduction |
---|
8 | |
---|
9 | 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. |
---|
10 | |
---|
11 | === Examples |
---|
12 | |
---|
13 | ==== Sort a List |
---|
14 | |
---|
15 | If 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 | |
---|
47 | The pairing-heap egg is released under a BSD License. |
---|
48 | |
---|
49 | === Requirements |
---|
50 | |
---|
51 | This egg requires only the base chicken system. |
---|
52 | |
---|
53 | === Procedures |
---|
54 | |
---|
55 | ==== A Note on Compare Procedures |
---|
56 | |
---|
57 | 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 |
---|
58 | |
---|
59 | * -1 if {{OBJ1 < OBJ2}} |
---|
60 | * 0 if {{OBJ1 = OBJ2}} |
---|
61 | * 1 if {{OBJ1 > OBJ2}} |
---|
62 | |
---|
63 | Thus, 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 | |
---|
75 | 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: |
---|
76 | |
---|
77 | [procedure] (pairing-heap? OBJ) |
---|
78 | |
---|
79 | {{#f}} unless {{OBJ}} is a pairing heap. |
---|
80 | |
---|
81 | [procedure] (pairing-heap-empty COMPARE) |
---|
82 | |
---|
83 | Construct 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 | |
---|
91 | Returns the smallest element in the heap {{H}}. Completes in O(1) time. |
---|
92 | |
---|
93 | [procedure] (pairing-heap-insert OBJ H) |
---|
94 | |
---|
95 | Returns 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 | |
---|
99 | Returns 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 | |
---|
103 | 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.) |
---|
104 | |
---|
105 | [procedure] (pairing-heap-fold KONS KNIL H) |
---|
106 | |
---|
107 | 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 |
---|
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 | |
---|
115 | 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. |
---|
116 | |
---|
117 | === Version History |
---|
118 | |
---|
119 | ; Version 1.0 : Initial release. |
---|