K smallest / largest elements in O(N * log(K)) complexity (N - size of the collection)

Implicits.scala

object implicits {
  implicit class RichTraversable[A](traversable: Traversable[A]) {
    // collect k smallest elements in O(n*log(k)) time (n - length of the list, k - size of the window)
    def minK(k: Int)(implicit cmp: Ordering[A]): List[A] = {
      if (k < 1) return List.empty
      traversable
        .foldLeft(mutable.PriorityQueue.empty) {
          // window not filled yet so append current element
          case (window, x) if window.size < k =>
            window.enqueue(x)
            window
          // current element is bigger than any element in the window so discard it
          case (window, x) if cmp.compare(x, window.head) >= 0 =>
            window
          // discard biggest element from the window and append current element
          case (window, x) =>
            window.dequeue()
            window.enqueue(x)
            window
        }
        .toList
        .sorted
    }

    // collect k largest elements in O(n*log(k)) time (n - length of the list, k - size of the window)
    def maxK(k: Int)(implicit cmp: Ordering[A]): List[A] = {
      // semantically same as the min method but uses reverse ordering
      minK(k)((x: A, y: A) => cmp.compare(y, x))
    }
  }
}