A priority queue implemented over a heap would be more efficient than a sorted set, in general. With a heap, you have constant time access to the smallest (WLOG) element in the heap at all times. Removing it costs a fixed O(lg n). A sorted set (especially one that's being modified) isn't necessarily going to allow you to find the smallest in constant time, and it's still going to require you O(lg n) to do the removals.
To the best of my knowledge, clojure nor clojure-contrib contain a heap implementation. I wrote one myself as part of an exercise (I implemented a simple Huffman-coder), but I'm not sure it's release quality. Otherwise, I'd be happy to donate it to contrib. Maybe I'll try to clean it up and send it off for a review. Mark On Dec 7, 11:29 pm, ataggart <alex.tagg...@gmail.com> wrote: > On Dec 7, 4:19 pm, ajay <ajgop...@gmail.com> wrote: > > > Hi all, > > > I am new to FP in general and I am trying to pick up Clojure. I am > > having trouble thinking in FP terms. > > > I am trying to implement the Dijkstra algorithm for shortest paths in > > Graph in Clojure. If this succeeds, I will implement all the advanced > > graph algos I am learning in this course in Clojure and post in > > online. > > > My concerns regarding implementing Dijkstra in Clojure are following: > > > 1. The way I've learnt Dijkstra, there is a distance array and we keep > > on updating it if we find a shorter path. Since, things are immutable, > > how do I do it? > > You call functions that give you a new, modified version of the input > collection. > (conj [1 2 3] 4) ;=> [1 2 3 4] > > And you can use atoms to hold a reference to a collection. Just > depends on how you want to use them. > > > 2. Does Clojure have a Priority Queue data structure inbuilt. I would > > need that for Dijkstra algorithm. > > I think sorted-set or sorted-set-by should suffice. If not, you could > make one or see if there's on in contrib somewhere. > > > > > > > Thanks, > > Ajay G. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
