求Scala可用的MinMaxPriorityQueue实现库（替代Guava版本）

Hey there! I totally get the frustration of hunting for a Scala-native version of Guava's handy MaxMinPriorityQueue and hitting dead ends with SBT dependencies. Let's walk through your options to get this sorted:

Option 1: Use Guava Directly (Scala-Java Interop) #

First off, you don't necessarily need a "Scala-specific" package here—Scala plays nicely with Java libraries, and Guava's MaxMinPriorityQueue works perfectly well in Scala projects. If your SBT build was failing, it's likely a dependency configuration issue.

To add Guava to your SBT project, just drop this line in your build.sbt:

libraryDependencies += "com.google.guava" % "guava" % "32.1.3-jre" // Use the latest stable version

Then in your Scala code, you can use it just like you would in Java, with minimal adjustments:

import com.google.common.collect.MaxMinPriorityQueue

// Create a queue for integers
val queue = MaxMinPriorityQueue.create[Int]()
queue.add(5)
queue.add(2)
queue.add(8)

println(queue.peekFirst()) // Gets the smallest element: 2
println(queue.peekLast())  // Gets the largest element: 8

If you still run into build issues, double-check that your Scala version is compatible with the Guava version you're using—most recent Guava releases work with Scala 2.12+, and Scala 3 as well.

Option 2: Roll Your Own Minimal Implementation #

If you'd prefer a pure Scala solution without relying on Java libraries, you can simulate a MaxMinPriorityQueue using two standard Scala PriorityQueues: one for the min-heap and one for the max-heap. You'll just need to keep them in sync when adding/removing elements.

Here's a quick, simplified example:

import scala.collection.mutable

class ScalaMaxMinPriorityQueue[T](implicit ord: Ordering[T]) {
  private val minHeap = mutable.PriorityQueue.empty[T](ord.reverse) // Min-heap
  private val maxHeap = mutable.PriorityQueue.empty[T](ord)        // Max-heap
  private val elementCount = mutable.Map[T, Int].empty

  def add(element: T): Unit = {
    minHeap.enqueue(element)
    maxHeap.enqueue(element)
    elementCount.update(element, elementCount.getOrElse(element, 0) + 1)
  }

  def peekFirst(): Option[T] = if (minHeap.nonEmpty) Some(minHeap.head) else None
  def peekLast(): Option[T] = if (maxHeap.nonEmpty) Some(maxHeap.head) else None

  def pollFirst(): Option[T] = {
    if (minHeap.isEmpty) None
    else {
      val elem = minHeap.dequeue()
      decrementCount(elem)
      cleanupHeaps()
      Some(elem)
    }
  }

  def pollLast(): Option[T] = {
    if (maxHeap.isEmpty) None
    else {
      val elem = maxHeap.dequeue()
      decrementCount(elem)
      cleanupHeaps()
      Some(elem)
    }
  }

  private def decrementCount(elem: T): Unit = {
    elementCount.update(elem, elementCount(elem) - 1)
    if (elementCount(elem) == 0) elementCount.remove(elem)
  }

  private def cleanupHeaps(): Unit = {
    // Remove elements from minHeap that are no longer in elementCount
    while (minHeap.nonEmpty && !elementCount.contains(minHeap.head)) minHeap.dequeue()
    // Remove elements from maxHeap that are no longer in elementCount
    while (maxHeap.nonEmpty && !elementCount.contains(maxHeap.head)) maxHeap.dequeue()
  }
}

This is a basic version—you can expand it with more features like size checks, clear methods, etc., based on your needs.

Option 3: Third-Party Scala Collections Libraries #

While there's no widely adopted standalone Scala library for MaxMinPriorityQueue, some functional Scala collections libraries let you build similar structures:

• Cats Collections: You can combine two PriorityQueue instances (one ordered normally, one reversed) to mimic the behavior, similar to the custom implementation above.
• Scala Collection Contrib: This extension to the standard library has some advanced collection types, though it doesn't have a direct MaxMinPriorityQueue—you'd still need to combine existing structures.

At the end of the day, using Guava directly is usually the quickest and most reliable solution, since it's battle-tested and requires minimal setup once you fix the dependency issue.

内容的提问来源于stack exchange，提问作者Alejandro Alcalde