Wie benutzt man Priority Queues in Scala?

Question

Ich versuche A * Suche in Scala (Version 2.10) zu implementieren, aber ich bin in eine Mauer gerannt - ich kann nicht herausfinden, wie man Scala's Priority Queue benutzt. Es scheint wie eine einfache Aufgabe, aber die Suche auf Google ergab nichts (außer für ein einzelnes Codebeispiel, das in Version 2.8 nicht mehr funktioniert)

Ich habe eine Reihe von Quadraten, vertreten durch (Int, Int) s, und ich müssen Sie sie mit Prioritäten einfügen, die durch Int s dargestellt werden. In Python ist es ziemlich einfach, da Sie nur eine Liste von Schlüssel-, Wert-Paaren haben und die heapq-Funktionen benutzen, um sie zu sortieren. Aber es scheint, dass Scalas Tupel nicht einmal vergleichbar sind.

Also, wie machst du das? Ich bin überrascht von dem vollständigen Mangel an Online-Informationen, wie einfach es sein sollte.

Answer 1

Es gibt eigentlich pre-defined lexicographical order for tuples - but you need to import it:

import scala.math.Ordering.Implicits._ 

Darüber hinaus können Sie Ihre eigene Ordnung definieren. Angenommen, ich möchte Tupeln arrangieren, basierend auf der Differenz zwischen dem ersten und dem zweiten Element des Tupels:

scala> import scala.collection.mutable.PriorityQueue 
// import scala.collection.mutable.PriorityQueue 

scala> def diff(t2: (Int,Int)) = math.abs(t2._1 - t2._2) 
// diff: (t2: (Int, Int))Int 

scala> val x = new PriorityQueue[(Int, Int)]()(Ordering.by(diff)) 
// x: scala.collection.mutable.PriorityQueue[(Int, Int)] = PriorityQueue() 

scala> x.enqueue(1 -> 1) 

scala> x.enqueue(1 -> 2) 

scala> x.enqueue(1 -> 3) 

scala> x.enqueue(1 -> 4) 

scala> x.enqueue(1 -> 0) 

scala> x 
// res5: scala.collection.mutable.PriorityQueue[(Int, Int)] = PriorityQueue((1,4), (1,3), (1,2), (1,1), (1,0)) 

Answer 2

In der Tat gibt es keine implizite Ordnung auf Paaren von ganzen Zahlen (a, b). Was würde es sein? Vielleicht sind sie beide positiv und du kannst (a - 1.0/b) benutzen? Oder sind sie nicht, und Sie können verwenden, was (a + atan (b/pi))? Wenn Sie eine Bestellung im Sinn haben, können Sie Ihre Paare in einem Typ verpacken, der Ihre Bestellung enthält.