bmizerany/perks — pull request #3 by blinsay (2013-06-21 17:01:00+00:00)
Title: Gave `topk` some love

I got a little inspired yesterday and gave the `topk` package some love. The version that was here before used a map and a pointer to the minimum element, which *almost* works. Unfortunately it falls apart when you repeatedly update the minimum element so that it's no longer the minumum. I replaced it with a map that indexes into a priority-queue, so that you can always track the minimum element as updates are applied.

There's also a shameless link in there to a blog post I wrote about this paper, but I think it's fairly helpful. ;)