tag:blogger.com,1999:blog-1175266939384385294.post3834034764234854492..comments2023-10-21T05:51:00.709-07:00Comments on (within parens...): Priority Queues in CLMarco Antoniottihttp://www.blogger.com/profile/06513735748852658637noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-1175266939384385294.post-58067415987004951162012-12-14T08:41:04.507-08:002012-12-14T08:41:04.507-08:00What is the index is something that only the queue...What is the index is something that only the queue implementation know.<br /><br />For an implementation based on a vector the index will be for example the numeric index into the array.<br /><br />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.<br /><br />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.<br /><br />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).6502https://www.blogger.com/profile/05363357723920755709noreply@blogger.comtag:blogger.com,1999:blog-1175266939384385294.post-56803368859495510642012-12-13T04:25:08.819-08:002012-12-13T04:25:08.819-08:00Hi sfrank,
can you post the github pointer to the...Hi sfrank,<br /><br />can you post the github pointer to the library?<br /><br />And yes. It is unclear how "extendable" it is. Maybe it'd be better to post this comment of the cdr-discuss mailing list?<br /><br />MA<br />Marco Antoniottihttps://www.blogger.com/profile/06513735748852658637noreply@blogger.comtag:blogger.com,1999:blog-1175266939384385294.post-83808665594076674612012-12-13T04:23:15.135-08:002012-12-13T04:23:15.135-08:00Yes. But the notion of "index of an element&q...Yes. But the notion of "index of an element" is not-so-defined. That is the problem.<br /><br />MAMarco Antoniottihttps://www.blogger.com/profile/06513735748852658637noreply@blogger.comtag:blogger.com,1999:blog-1175266939384385294.post-46162325760681522902012-12-11T11:30:26.764-08:002012-12-11T11:30:26.764-08:00I wish Ingvar would maintain his previous CLR libr...I wish Ingvar would maintain his previous CLR library, genhash. It's been unreachable for months.Xachhttps://www.blogger.com/profile/04498567730331742642noreply@blogger.comtag:blogger.com,1999:blog-1175266939384385294.post-26557906516856226922012-12-10T22:41:25.637-08:002012-12-10T22:41:25.637-08:00My minheap library (which is available on github a...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.<br /><br />Though from the linked PDF I don't really see how the described heaps in CDR12 are extendable (but maybe I need more coffee first).sfrankhttps://www.blogger.com/profile/00129221717015830457noreply@blogger.comtag:blogger.com,1999:blog-1175266939384385294.post-73608804192645470142012-12-10T10:20:09.324-08:002012-12-10T10:20:09.324-08:00I don't have CLR but if the operations are mea...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.<br /><br />In 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.<br /><br />Where to store the index is up to the user (normally using for example a slot of the element is efficient).<br /><br />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.<br /><br />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.<br /><br />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)) ... ).<br />6502https://www.blogger.com/profile/05363357723920755709noreply@blogger.com