用三叉小顶堆保留搜索得分最高的 K 个文档

40  // prevents instantiation41  TopScoreDocCollector(42      int numHits, ScoreDoc after, int totalHitsThreshold, MaxScoreAccumulator minScoreAcc) {43    super(null);44    this.heap = new TernaryLongHeap(numHits, DocScoreEncoder.LEAST_COMPETITIVE_CODE);45    this.after = after;46    this.totalHitsThreshold = totalHitsThreshold;47    this.minScoreAcc = minScoreAcc;48  }

113        if (score <= topScore) {114          // Note: for queries that match lots of hits, this is the common case: most hits are not115          // competitive.116          if (hitCountSoFar == totalHitsThreshold + 1) {117            // we just exceeded totalHitsThreshold, we can start setting the min118            // competitive score now119            updateMinCompetitiveScore(scorer);120          }121122          // Since docs are returned in-order (i.e., increasing doc Id), a document123          // with equal score to pqTop.score cannot compete since HitQueue favors124          // documents with lower doc Ids. Therefore reject those docs too.125        } else {126          collectCompetitiveHit(doc, score);127        }128      }129130      private void collectCompetitiveHit(int doc, float score) throws IOException {131        final long code = DocScoreEncoder.encode(doc + docBase, score);132        topCode = heap.updateTop(code);133        topScore = DocScoreEncoder.toScore(topCode);134        updateMinCompetitiveScore(scorer);

31  static long encode(int docId, float score) {32    return (((long) NumericUtils.floatToSortableInt(score)) << 32) | (Integer.MAX_VALUE - docId);33  }3435  static float toScore(long value) {36    return NumericUtils.sortableIntToFloat((int) (value >>> 32));37  }3839  static int docId(long value) {40    return Integer.MAX_VALUE - ((int) value);41  }

151  public long updateTop(long value) {152    heap[1] = value;153    TernaryLongHeap.downHeap(heap, 1, size, ARITY);154    return heap[1];155  }

228      int lastChild = Math.min(firstChild + arity - 1, size);229230      // find the smallest child in [firstChild, lastChild]231      int best = firstChild;232      long bestVal = heap[firstChild];233234      for (int c = firstChild + 1; c <= lastChild; c++) {235        final long v = heap[c];236        if (v < bestVal) {237          bestVal = v;238          best = c;239        }240      }241242      if (bestVal >= value) break;243244      heap[i] = bestVal;245      i = best;246    }247    heap[i] = value; // install saved value248  }

187  @Override188  protected void populateResults(ScoreDoc[] results, int howMany) {189    for (int i = howMany - 1; i >= 0; i--) {190      long encode = heap.pop();191      results[i] = new ScoreDoc(DocScoreEncoder.docId(encode), DocScoreEncoder.toScore(encode));192    }193  }