If "normal" is a binary heap with log(n) for most things, no. This is better.
You can check out the paper(s) I based it on included in the project. It has runtimes equivalent to Fibonacci Heap except that Fib-Heaps only have amortized worst case. insert: O(1) findMin: O(1) meld: <--- i don't remember if I got around to O(1) ... was so fast even with O(logn) deleteMin: O(logn) all in the paper. One exception is that I was starting to experiment with the decreaseKey, deleteKey ideas that can reach in to the middle. Those are outside the paper and are amortized, at least right now. Again, I also didn't know whether a map-like analogy was right. I've seen other Heap implementations that are more like a set. That is, you put some structure in that contains it's own data. Right now the key and the data are separate. On Tue, Feb 2, 2010 at 3:05 PM, ajay gopalakrishnan <[email protected]>wrote: > What is the time and space complexity for your implementation? Equals the > normal non-functional implementation? > > On Tue, Feb 2, 2010 at 7:31 AM, e <[email protected]> wrote: > >> i was messing around a while back with this: >> http://code.google.com/p/jc-pheap/ >> >> the algorithms work, but it's probably in a between-state. I wasn't sure >> what the interface should look like exactly, and I was recently adding >> support for duplicate keys (but I wasn't sure if I should have two >> structures or one ... the latter being more of the multimap I'm describing). >> >> Oh, and I was starting to work on decreaseKey(), too ... but the runtime >> is still, likely amortized for that one. I actually had an idea that I'm >> not sure has ever been done before to make that operation even more baked. >> Fun stuff. >> >> The project does not depend on clojure, but shows clojure code as an >> example. If I recall, it all works. Hmmmm, maybe I'll get back into >> working on it and variations, tho. >> >> On Tue, Dec 15, 2009 at 5:16 AM, ataggart <[email protected]> wrote: >> >>> >>> >>> On Dec 15, 1:49 am, ataggart <[email protected]> wrote: >>> > On Dec 14, 5:48 am, Mark Tomko <[email protected]> wrote: >>> > >>> > > I wrote this implementation of a heap (or priority queue) in pure >>> > > Clojure: >>> > >>> > >http://pastebin.com/m2ab1ad5a >>> > >>> > > It's probably not of any quality sufficient to be make it to the >>> > > contrib package, but it seems to work. Any thoughts on how it might >>> > > be improved? >>> > >>> > > Thanks, >>> > > Mark >>> > >>> > Ideally such a collection would be usable with existing functions, >>> > e.g. pop, peek. To accomplish that you really need to implement >>> > against the expected java interfaces. >>> > >>> > I've been playing with the deftype/defprotocol stuff in the "new" >>> > branch, so I figured I'd try to apply that to this problem. This is >>> > what I came up with: >>> > >>> > http://gist.github.com/256815 >>> >>> To be clear, my implementation just uses a sorted list, not a true >>> heap tree. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Clojure" group. >>> To post to this group, send email to [email protected] >>> Note that posts from new members are moderated - please be patient with >>> your first post. >>> To unsubscribe from this group, send email to >>> [email protected]<clojure%[email protected]> >>> For more options, visit this group at >>> http://groups.google.com/group/clojure?hl=en >>> >> >> -- >> You received this message because you are subscribed to the Google >> Groups "Clojure" group. >> To post to this group, send email to [email protected] >> Note that posts from new members are moderated - please be patient with >> your first post. >> To unsubscribe from this group, send email to >> [email protected]<clojure%[email protected]> >> For more options, visit this group at >> http://groups.google.com/group/clojure?hl=en >> > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to [email protected] > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > [email protected]<clojure%[email protected]> > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/clojure?hl=en
