code: 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];
        }
      }
    }
docs: Quickselects the top k elements from the 2k elements in the buffer. O(k) expected time, O(k log
  k) worst case.