There is a new CDR by Ingvar Mattsson proposing the specification of a simple heap (priority queue) interface for CL: CDR 12: Generic extendable heaps for Common Lisp.
The question in this case is how to support the INCREASE-KEY (or DECREASE-KEY) operation mentioned by CLRS. It is known that such support is application-dependent, however, it would be nice to make it explicit.
Just to show my age, about 20 years ago, I did write a priority queue implementation that is still available in the CMU AI Repository. In that ancient implementation, a hash table was used internally to support the INCREASE-KEY/DECREASE-KEY operation and I always wondered whether there is a better interface to aid the maintenance of the heap invariants while keeping the performance guarantees.
Any suggestions?
(Cheers)
I don't have CLR but if the operations are meant to change the relative ordering of an element in respect other elements then you just need to be provide the user with a way to know the index of an element.
ReplyDeleteIn an heap implementation I wrote this is done by providing a "tracking" function at heap creation. The function is called passing element and index or element and NIL when the element is removed from the heap.
Where to store the index is up to the user (normally using for example a slot of the element is efficient).
The user then can also call (heap-fix heap index) to update the heap in case the internal state of the element is changed and this could change the ordering in respect to other elements.
With this approach the overhead for who doesn't need updating is minimal (just the check that tracking doesn't need to be called) and who needs it instead only incurs in O(1) space per element without decreasing the heap performance.
Index tracking also allows extending the pop operation for an element that's not the topmost by using (defun heap-pop (heap &optional (index 0)) ... ).
Yes. But the notion of "index of an element" is not-so-defined. That is the problem.
DeleteMA
What is the index is something that only the queue implementation know.
DeleteFor an implementation based on a vector the index will be for example the numeric index into the array.
The index is simply something that allows a user of the queue to ask later to remove a specific item or inform that its priority changed so it can bubble to a different position.
This way the user doesn't need to know how the priority queue is represented and the queue doesn't need to know how the elements are represented and more specifically doesn't need to search for them.
Nothing is free of course and the extra price to pay (if you want the extra ops) is a call to (set-index element index) every time that is required by the queue and a place where to store this index. Leaving the index storage problem to the user the operation can trivially be implemented as O(1).
My minheap library (which is available on github and in quicklisp) implements several advanced (and not so common) heap data structures (with priority queue functionality, decrease key and meld operations). Though I used a hard coded < on fixnums because I needed maximum performance, one could simply add a comparison function to the heap class and use that instead, if one wants a more general comparison method. Maybe this library could be a starting point for further inspiration.
ReplyDeleteThough from the linked PDF I don't really see how the described heaps in CDR12 are extendable (but maybe I need more coffee first).
Hi sfrank,
Deletecan you post the github pointer to the library?
And yes. It is unclear how "extendable" it is. Maybe it'd be better to post this comment of the cdr-discuss mailing list?
MA
I wish Ingvar would maintain his previous CLR library, genhash. It's been unreachable for months.
ReplyDelete