14th June 2017, 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:
   June 15, 2017 at 8:04 pm

   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() ) {
       b.add(x);
       b.poll();
     }
   }
   

   1. Daniel Lemire says:
      June 16, 2017 at 1:23 pm

      I have taken the liberty of making your code look pretty.