On Tue, Aug 19, 2014 at 4:10 PM, Dan Stromberg <drsali...@gmail.com> wrote: > On Tue, Aug 19, 2014 at 4:05 PM, Dan Stromberg <drsali...@gmail.com> wrote: >> When you use heapq, are you putting all the values in the heap, or >> just up to n at a time (evicting the worst value, one at a time as you >> go)? If you're doing the former, it's basically a heapsort which >> probably won't beat timsort. If you're doing the latter, that should >> be pretty good. > > It just occurred to me that evicting the highest value each step of > the way might be expensive with a traditional heap (since the value at > the largest array index isn't necessarily the largest). I've > experimented with doing this using a treap a bit: > http://stromberg.dnsalias.org/~strombrg/treap/ You might try that.
Or more directly relevant: http://stromberg.dnsalias.org/~strombrg/highest/ -- https://mail.python.org/mailman/listinfo/python-list
