Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 364 lines (253 sloc) 11.824 kb
78824d05 »
2012-06-09 README updates.
1 CL-HEAP
2 =======
87f8f973 » rneeser
2009-03-24 Initial import.
3
4 CL-HEAP is a Common Lisp library that provides efficient priority
5 queue and heap implementations. Heaps are tree data structure in which
6 any child, c, of a parent, p, obeys the relation p R c, for some
7 relation R (often less-than or greater-than). Heaps can be used
8 directly as priority queues, and are important components of many
9 algorithms, like those for finding shortest paths and calculating
10 minimum spanning trees.
11
12 The library is simple to use. Here's an example covering most of the
13 priority queue functionality:
14
e7ee13c6 »
2012-06-09 README tests.
15 ```lisp
1507ad02 »
2012-06-09 More readme updates.
16 (defparameter *queue* (make-instance 'cl-heap:priority-queue))
17
87f8f973 » rneeser
2009-03-24 Initial import.
18 (cl-heap:enqueue *queue* 'test 15) ; Enqueue the item with the priority of 15.
19 (cl-heap:enqueue *queue* 'this -5)
20 (cl-heap:enqueue *queue* 'a 10)
21 (cl-heap:enqueue *queue* 'is 5)
22
23 (cl-heap:peep-at-queue *queue*) => 'this
24
25 (cl-heap:dequeue *queue*) => 'this
26 (cl-heap:dequeue *queue*) => 'is
27 (cl-heap:dequeue *queue*) => 'a
28 (cl-heap:dequeue *queue*) => 'test
1507ad02 »
2012-06-09 More readme updates.
29 ```
87f8f973 » rneeser
2009-03-24 Initial import.
30
31 The library provides an implementation of an array-based binary heap -
32 offering O(log(n)) times for most operations - and the Fibonacci
33 heap. While any sequence of arbitrary operations on a Fibonacci heap
34 occur in amortised logarithmic time, many common operations occur in
35 constant and amortised constant time. See below for further
36 details. The Fibonacci heap should generally be your heap of choice
37 from this library.
38
39
78824d05 »
2012-06-09 README updates.
40 Installation and Usage
41 ----------------------
87f8f973 » rneeser
2009-03-24 Initial import.
42
43 CL-HEAP depends on XLUNIT, which is used to perform unit
44 testing. CL-HEAP has been tested and is known to run on SBCL. If
45 you've tried this on other compilers and it runs successfully, please
46 let me know. The library can be installed using ASDF-INSTALL:
47
1507ad02 »
2012-06-09 More readme updates.
48 ```lisp
87f8f973 » rneeser
2009-03-24 Initial import.
49 (require 'asdf-install)
50 (asdf-install:install 'cl-heap)
1507ad02 »
2012-06-09 More readme updates.
51 ```
87f8f973 » rneeser
2009-03-24 Initial import.
52
53 And the library can then be loaded with ASDF:
54
1507ad02 »
2012-06-09 More readme updates.
55 ```lisp
9bb52adb »
2012-06-09 README tests.
56 (asdf:load-system 'cl-heap)
1507ad02 »
2012-06-09 More readme updates.
57 ```
87f8f973 » rneeser
2009-03-24 Initial import.
58
78824d05 »
2012-06-09 README updates.
59 Test Suite
60 ----------
87f8f973 » rneeser
2009-03-24 Initial import.
61
62 CL-HEAP comes with a test suite. The tests for the various classes can
63 be performed as follows:
64
1507ad02 »
2012-06-09 More readme updates.
65 ```lisp
87f8f973 » rneeser
2009-03-24 Initial import.
66 (xlunit:textui-test-run (xlunit:get-suite cl-heap:fibonacci-test))
67 (xlunit:textui-test-run (xlunit:get-suite cl-heap:binary-test))
68 (xlunit:textui-test-run (xlunit:get-suite cl-heap:priority-queue-test))
1507ad02 »
2012-06-09 More readme updates.
69 ```
87f8f973 » rneeser
2009-03-24 Initial import.
70
78824d05 »
2012-06-09 README updates.
71 The PRIORITY-QUEUE Class
72 ------------------------
87f8f973 » rneeser
2009-03-24 Initial import.
73
74 This priority queue is a container for items in which all the items
75 are sorted by some given priority. We implement the priority queue
76 using a Fibonacci heap.
77
78 MAKE-INSTANCE accepts the argument :sort-fun to provide the function
79 which the items' priorities are sorted by. This defaults to #'<, which
80 will cause the queue to always return the item of lowest priority.
81
9bb52adb »
2012-06-09 README tests.
82 (ENQUEUE queue item priority)
83
84 Adds the item to the queue at the given priority. Returns a
85 list containing first the item's priority, then the item
86 itself. Running time: O(1)
87f8f973 » rneeser
2009-03-24 Initial import.
87
88 (DEQUEUE queue)
89 Removes the item of lowest priority from the queue. Running
90 time: amortised O(log(n))
91
92 (PEEP-AT-QUEUE queue)
93 Returns the item of lowest priority from the queue, without
94 modifying the queue. Running time: O(1)
95
96 (EMPTY-QUEUE queue)
97 Removes all items from the queue. Returns the heap. Running
98 time: O(1)
99
100 (QUEUE-SIZE queue)
101 Returns the number of items in the queue. Running time: O(1)
102
103
78824d05 »
2012-06-09 README updates.
104 The HEAP Class
105 --------------
87f8f973 » rneeser
2009-03-24 Initial import.
106
107 HEAP provides functionality common to the two heap classes implement
108 by CL-HEAP. Each heap implementation accepts at least two arguments to
109 MAKE-INSTANCE: :key and :sort-fun. :sort-fun supplies the function to
e7ee13c6 »
2012-06-09 README tests.
110 be used when comparing two objects to each other, and defaults to #'<.
111 :key gives a function which should be first applied to the
87f8f973 » rneeser
2009-03-24 Initial import.
112 elements in the HEAP before comparing them using the sorting
113 function. :key defaults to #'identity. These functions can be accessed
114 using HEAP-KEY and HEAP-SORTING-FUNCTION.
115
116 Both of the heap implementations obey the same interface:
117
118 (HEAP-KEY heap)
119 Returns the function passed as the :key argument to the heap.
120
121 (HEAP-SORTING-FUNCTION heap)
122 Returns the function used to sort the elements in the heap.
123
124 (HEAP-SIZE heap)
125 Returns the number of elements in the heap.
126
127 (EMPTY-HEAP heap)
128 Removes all items from the heap, and returns the heap.
129
130 (IS-EMPTY-HEAP-P heap)
131 Returns true iff the heap contains no elements.
132
133 (ADD-TO-HEAP heap item)
134 Adds the given item to the heap. Returns two values: first
135 the item itself, and then some index-key which can be used by
136 DECREASE-KEY and DELETE-KEY to identify which values should
137 be affected by these operations. See below for an example.
138
139 (ADD-ALL-TO-HEAP heap items)
140 Adds all items in the list to the heap, as if by repeated
141 calls to ADD-TO-HEAP. ADD-ALL-TO-HEAP can often be
142 implemented more efficiently, though, than by merely
143 executing consecutive calls to ADD-TO-HEAP directly. Returns
144 the heap object.
145
146 (PEEP-AT-HEAP heap)
147 Returns the minimum item in the heap, without modifying the
148 heap.
149
150 (POP-HEAP heap)
151 Removes the smallest item in the heap, and returns it.
152
153 (MERGE-HEAPS first second)
154 Returns a new heap which contains all the items in both
155 heaps. Only heaps which use the same HEAP-KEY and
156 HEAP-SORTING-FUNCTION can be merged, otherwise a HEAP-ERROR
157 is signalled.
158
159 (NMERGE-HEAPS first second)
160 Destructively creates a new heap which contains the items in
161 both heaps. Only heaps which use the same HEAP-KEY and
162 HEAP-SORTING-FUNCTION can be merged, otherwise a HEAP-ERROR
163 is signalled.
164
165 (DECREASE-KEY heap item-index value)
166 Allows you to specify an item in the heap whose value should
167 be decreased. ITEM-INDEX is the second value returned by
168 ADD-TO-HEAP, and VALUE should be smaller than the items
169 current value, or a KEY-ERROR will be signalled. Returns the
170 heap. See below for an example.
171
172 (DELETE-FROM-HEAP heap item-index)
173 Allows you to specify an arbitrary item to remove from the
174 heap. ITEM-INDEX is the second value returned by ADD-TO-HEAP.
175
176 DECREASE-KEY requires that HEAP-KEY is either the function IDENTITY,
177 or a function that accepts an optional second argument, which will be
178 the value of the new key. For instance, if the elements in the heap
179 are lists, and they are to be sorted by the first element in the list,
180 an appropriate HEAP-KEY could be:
181
182 (lambda (item &optional new-value)
183 (if new-value
184 (setf (first item) new-value)
185 (first item)))
186
187 Of course, if DECREASE-KEY is not going to be used, then #'first
188 itself could simply be used as the HEAP-KEY.
189
190
78824d05 »
2012-06-09 README updates.
191 The BINARY-HEAP Class
192 ---------------------
87f8f973 » rneeser
2009-03-24 Initial import.
193
194 BINARY-HEAP is constructed in the typical fashion, using an array. The
195 BINARY-HEAP MAKE-INSTANCE call accepts an extra argument, :size, which
196 sets the data array's initial size.
197
198 Note that DECREASE-KEY and DELETE-FROM-HEAP are not very useful
199 operations on this heap: while they work, the required index-keys may
200 be invalidated as soon as any heap operation is performed. If you do
201 want to make use of DELETE-FROM-HEAP or DECREASE-KEY, consider using
202 FIBONACCI-HEAP instead.
203
204 BINARY-HEAP provides an extra function to the above API:
205
206 (BINARY-HEAP-EXTENSION-FACTOR heap)
207 The percentage at which the space allocated for data in the
208 heap should grow at once that space has been exceeded. This
209 defaults to 50.
210
211 Here are the Big-Oh running times for the heap API, where n and m are
212 the sizes of various heaps.
213
214 (HEAP-SIZE heap) => O(1)
215
216 (EMPTY-HEAP heap) => O(1)
217
218 (IS-EMPTY-HEAP-P heap) => O(1)
219
220 (ADD-TO-HEAP heap item) => O(log(n))
221
222 (ADD-ALL-TO-HEAP heap items) => O(n)
223
224 (PEEP-AT-HEAP heap) => O(1)
225
226 (POP-HEAP heap) => O(log(n))
227
228 (MERGE-HEAPS first second) => O(n + m + log(n + m))
229
230 (NMERGE-HEAPS first second) => O(m + log(n + m))
231
232 (DECREASE-KEY heap item-index value) => O(log(n))
233
234 (DELETE-FROM-HEAP heap item-index) => O(log(n))
235
236
78824d05 »
2012-06-09 README updates.
237 The FIBONACCI-HEAP Class
238 ------------------------
87f8f973 » rneeser
2009-03-24 Initial import.
239
240 The details of the Fibonacci heap are given in "Fibonacci Heaps and
241 Their Uses in Improved Network Optimization Algorithms", by Fredman
242 and Tarjan (see references below).
243
244 The Fibonacci heap has some interesting time constraints, and should
245 generally be used instead of BINARY-HEAP.
246
247 Here are the Big-Oh running times for the heap API, where n and m are
248 the sizes of various heaps.
249
250 (HEAP-SIZE heap) => O(1)
251
252 (EMPTY-HEAP heap) => O(1)
253
254 (IS-EMPTY-HEAP-P heap) => O(1)
255
256 (ADD-TO-HEAP heap item) => O(1)
257
258 (ADD-ALL-TO-HEAP heap items) => O(n)
259
260 (PEEP-AT-HEAP heap) => O(1)
261
262 (POP-HEAP heap) => amortised O(log(n))
263
264 (MERGE-HEAPS first second) => O(m + n)
265
266 (NMERGE-HEAPS first second) => O(1)
267
268 (DECREASE-KEY heap item-index value) => amortised O(1)
269
270 (DELETE-FROM-HEAP heap item-index) => amortised O(1), except where
271 the deleted item was the minimum
272 item, in which case it is
273 amortised O(log(n))
274
275
78824d05 »
2012-06-09 README updates.
276 Examples of Use
277 ---------------
87f8f973 » rneeser
2009-03-24 Initial import.
278
279 A heap can be created quite simply:
280
281 (defparameter *heap* (make-instance 'cl-heap:fibonacci-heap))
282
283 This will create a heap where the elements are ordered using
284 #'<. Elements can be added one at a time using ADD-TO-HEAP:
285
286 (cl-heap:add-to-heap *heap* 1)
287
288 or, in a batch.
289
290 (cl-heap:add-all-to-heap *heap* '(6 4 7 3 2 0))
291
292 The minimum item in this heap can easily by seen using PEEP-AT-HEEP,
293 which will not modify the heap in any way:
294
295 (cl-heap:peep-at-heap *heap*) => 0
296
297 The minimum item can be removed from the heap using POP-HEAP:
298
299 (cl-heap:pop-heap *heap*) => 0
300
301 Heaps can be used to sort items:
302
303 (let ((heap (make-instance 'cl-heap:fibonacci-heap)))
304 (cl-heap:add-all-to-heap heap (loop for i from 1 upto 10 collect (random 100)))
305 (loop while (not (cl-heap:is-empty-heap-p heap)) collect (cl-heap:pop-heap heap)))
306
307 => (14 19 30 32 38 64 74 90 96 98)
308
309 A max-heap can be constructed as follows:
310
311 (defparameter *heap* (make-instance 'cl-heap:fibonacci-heap :sort-fun #'>))
312
313 And this will order things from most to least:
314
315 (let ((heap (make-instance 'cl-heap:fibonacci-heap :sort-fun #'>)))
316 (cl-heap:add-all-to-heap heap (loop for i from 1 upto 10 collect (random 100)))
317 (loop while (not (cl-heap:is-empty-heap-p heap)) collect (cl-heap:pop-heap heap)))
318
319 => (69 68 64 60 37 34 30 7 6 1)
320
321 The heaps can contain arbitrary items. For instance, a heap whose
322 elements are all lists can be constructed as follows:
323
324 (defparameter *heap* (make-instance 'cl-heap:fibonacci-heap :key #'first))
325 (cl-heap:add-to-heap *heap* (list 5 'some 'arbitrary 'data))
326 (cl-heap:add-to-heap *heap* (list 4 'other 'data))
327 (cl-heap:pop-heap *heap*) => (4 other data)
328
329 DECREASE-KEY and DELETE-FROM-HEAP can be used as follows:
330
331 (defparameter *heap* (make-instance 'cl-heap:fibonacci-heap))
332 (cl-heap:add-all-to-heap *heap* '(5 3 4 2 1))
333 (let ((item-index (second (multiple-value-list (cl-heap:add-to-heap *heap* 10)))))
334 (format t "Smallest item: ~A~%" (cl-heap:peep-at-heap *heap*))
335 (cl-heap:decrease-key *heap* item-index 0)
336 (format t "Smallest item: ~A~%" (cl-heap:peep-at-heap *heap*)))
337
338 => nil
339 Smallest item: 1
340 Smallest item: 0
341
78824d05 »
2012-06-09 README updates.
342 License
343 -------
87f8f973 » rneeser
2009-03-24 Initial import.
344
345 CL-HEAP is free software: you can redistribute it and/or modify it
346 under the terms of the GNU General Public License as published by the
347 Free Software Foundation, either version 3 of the License, or (at your
348 option) any later version.
349
350 This program is distributed in the hope that it will be useful,
351 but WITHOUT ANY WARRANTY; without even the implied warranty of
352 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
353 GNU General Public License for more details.
354
355 You should have received a copy of the GNU General Public License
356 along with this program. If not, see <http://www.gnu.org/licenses/>.
357
358
78824d05 »
2012-06-09 README updates.
359 References
360 ----------
87f8f973 » rneeser
2009-03-24 Initial import.
361
362 M. L. Fredman and R. E. Tarjan. 1987. "Fibonacci Heaps and Their Uses
363 in Improved Network Optimizxation Algorithms". Journal of the
364 Association for Computing Machinery, Vol 34, No 3. pp 596 - 615
Something went wrong with that request. Please try again.