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 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 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
