Daniel Lemire's blog

, 2 min read

QuickSelect versus binary heap for top-k queries

2 thoughts on “QuickSelect versus binary heap for top-k queries”

  1. KWillets says:

    A lot hinges on the fact that the k-th value at most intermediate stages is a pretty good pivot for partitioning.

    I just tripled the speed of the FastPriorityQueue version by doing this:

    for (i = 128 ; i < 128 * blocks ; i++) {
      var x = rand(i);
      if ( x > b.peek() ) {
    1. I have taken the liberty of making your code look pretty.