> > > But here would be an interesting situation: what if all the Heap inserts > do end up being faster, but popping every element off is slower because > deleteMin()'s constant is so high? Well, then there's a cross-over point > that would be nice to know about. It might be better to use the heap, when > you only want, say, the top K things, but if you want the top K+1 things, > than it's cheaper to just sort them all. >
for completeness, I forgot about QuickSelect if *all* you want is the top K, and especially in an imperative setting: http://www.scribd.com/doc/4954930/Advanced-Topics-in-Sorting so I guess another part of the use case might be that different consumers want to get a potentially different top-K. So once a single heapification occurs, each consumer can have their own view and pop in O(k log(n)) time, for whatever k they want, reusing most of a shared data structure. --~--~---------~--~----~------------~-------~--~----~ 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 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 -~----------~----~----~----~------~----~------~--~---
