On Dec 8, 4:38 pm, ajay gopalakrishnan <ajgop...@gmail.com> wrote: > It might not be if the sorted set is internally represented as a tree. Then > the smallest element with the leaf of the tree (if tree is balanced) and > that is not accessible in O(1) time. > > > > ---------- Forwarded message ---------- > From: ataggart <alex.tagg...@gmail.com> > Date: Tue, Dec 8, 2009 at 6:22 PM > Subject: Re: Trouble implementing Dijkstra algorithm in Clojure > To: Clojure <clojure@googlegroups.com> > > On Dec 8, 11:38 am, Mark Tomko <mjt0...@gmail.com> wrote: > > 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. > > I would be very surprised if getting the first element from a sorted- > set wasn't ~O(1). > > -- > 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<clojure%2bunsubscr...@googlegroups.com > > For more options, visit this group > athttp://groups.google.com/group/clojure?hl=en
Ah yeah, wasn't thinking clearly. -- 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
