private void trim() {
    int left = 0;
    int right = 2 * k - 1;

    int minThresholdPosition = 0;
    // The leftmost position at which the greatest of the k lower elements
    // -- the new value of threshold -- might be found.

    int iterations = 0;
    int maxIterations = IntMath.log2(right - left, RoundingMode.CEILING) * 3;
    while (left < right) {
      int pivotIndex = (left + right + 1) >>> 1;

      int pivotNewIndex = partition(left, right, pivotIndex);

      if (pivotNewIndex > k) {
        right = pivotNewIndex - 1;
      } else if (pivotNewIndex < k) {
        left = Math.max(pivotNewIndex, left + 1);
        minThresholdPosition = pivotNewIndex;
      } else {
        break;
      }
      iterations++;
      if (iterations >= maxIterations) {
        // We've already taken O(k log k), let's make sure we don't take longer than O(k log k).
        Arrays.sort(buffer, left, right, comparator);
        break;
      }
    }
    bufferSize = k;

    threshold = buffer[minThresholdPosition];
    for (int i = minThresholdPosition + 1; i < k; i++) {
      if (comparator.compare(buffer[i], threshold) > 0) {
        threshold = buffer[i];
      }
    }
  }
private void trim() {
    int left = 0;
    int right = 2 * k - 1;

    int minThresholdPosition = 0;
    
    

    int iterations = 0;
    int maxIterations = IntMath.log2(right - left, RoundingMode.CEILING) * 3;
    while (left < right) {
      int pivotIndex = (left + right + 1) >>> 1;

      int pivotNewIndex = partition(left, right, pivotIndex);

      if (pivotNewIndex > k) {
        right = pivotNewIndex - 1;
      } else if (pivotNewIndex < k) {
        left = Math.max(pivotNewIndex, left + 1);
        minThresholdPosition = pivotNewIndex;
      } else {
        break;
      }
      iterations++;
      if (iterations >= maxIterations) {
        
        Arrays.sort(buffer, left, right, comparator);
        break;
      }
    }
    bufferSize = k;

    threshold = buffer[minThresholdPosition];
    for (int i = minThresholdPosition + 1; i < k; i++) {
      if (comparator.compare(buffer[i], threshold) > 0) {
        threshold = buffer[i];
      }
    }
  }
private void trim ( ) { int left = 0 ; int right = 2 * k - 1 ; int minThresholdPosition = 0 ; // The leftmost position at which the greatest of the k lower elements // -- the new value of threshold -- might be found. int iterations = 0 ; int maxIterations = IntMath . log2 ( right - left , RoundingMode . CEILING ) * 3 ; while ( left < right ) { int pivotIndex = ( left + right + 1 ) >>> 1 ; int pivotNewIndex = partition ( left , right , pivotIndex ) ; if ( pivotNewIndex > k ) { right = pivotNewIndex - 1 ; } else if ( pivotNewIndex < k ) { left = Math . max ( pivotNewIndex , left + 1 ) ; minThresholdPosition = pivotNewIndex ; } else { break ; } iterations ++ ; if ( iterations >= maxIterations ) { // We've already taken O(k log k), let's make sure we don't take longer than O(k log k). Arrays . sort ( buffer , left , right , comparator ) ; break ; } } bufferSize = k ; threshold = buffer [ minThresholdPosition ] ; for ( int i = minThresholdPosition + 1 ; i < k ; i ++ ) { if ( comparator . compare ( buffer [ i ] , threshold ) > 0 ) { threshold = buffer [ i ] ; } } }
Quickselects the top k elements from the 2k elements in the buffer. O(k) expected time, O(k log
k) worst case.
Quickselects the top k elements from the 2k elements in the buffer . O ( k ) expected time O ( k log k ) worst case .