Kolejka priorytetowa Scala uporządkowana, która ma zawsze najniższy numer jako nagłówek, kolejność rosnąca.

Question

Chciałbym otrzymać próbkę kodu, która zawiera rosnącą kolejność elementów w kolejce priorytetowej.

Chciałbym przechowywać Tuple2(Int, String) wewnątrz kolejki priorytetów, tak aby została zamówiona przez pierwszy element krotki w porządku rosnącym. Jeśli kolejka priorytetowa nazywa się pq i ja dzwonię pod numer pq.head Chciałbym uzyskać krotkę z najniższym numerem, to samo z wywoływaniem pq.dequeue.

scala> val pq = scala.collection.mutable.PriorityQueue[(Int, String)]() 
pq: scala.collection.mutable.PriorityQueue[(Int, String)] = PriorityQueue() 

scala> pq += Tuple2(8, "eight") 
res60: pq.type = PriorityQueue((8,eight)) 

scala> pq += Tuple2(4, "four") 
res61: pq.type = PriorityQueue((8,eight), (4,four)) 

scala> pq += Tuple2(7, "seven") 
res62: pq.type = PriorityQueue((8,eight), (4,four), (7,seven)) 

Jak zastosować kolejność rosnącą według pierwszego elementu w momencie wstawienia do powyższego?

Dzięki

Answer 1

PriorityQueue.apply i PriorityQueue.empty zarówno wziąć niejawny Ordering instancję, która będzie używana zamówić Contents-szef będzie „największym” wartość według tej kolejności. Dostajesz domyślną dla krotek, która jest leksykograficzną kolejnością elementów krotki, co nie jest tym, czego potrzebujesz, ponieważ stworzy krotkę z największym pierwszym elementem w głowie.

Istnieje kilka sposobów rozwiązania tego problemu. Najłatwiej jest po prostu zadzwonić pod numer .reverse w swojej kolejce, co da ci nową kolejkę o tej samej zawartości, ale w przeciwnej kolejności, co oznacza, że ​​krotka z najniższą wartością będzie głową.

Można również dostarczyć własną kolejność podczas tworzenia kolejki:

import scala.collection.mutable.PriorityQueue 

val pq = PriorityQueue.empty[(Int, String)](
    implicitly[Ordering[(Int, String)]].reverse 
) 

Lub jeśli wyraźnie nie chce drugi element jest konsultowany:

val pq = PriorityQueue.empty[(Int, String)](
    Ordering.by((_: (Int, String))._1).reverse 
) 

Jest to prawdopodobnie trochę bardziej wydajne niż cofanie kolejki, ale prawdopodobnie nie wystarczy, aby się martwić, więc powinieneś po prostu wybrać podejście, które uważasz za najbardziej eleganckie.

Answer 2

Z scaladoc:

Tylko metody dequeue i dequeueAll powróci metod w kolejności priorytetowej (podczas usuwania elementów z hałdy). Standardowe metody zbierania, w tym drop i iterator, usuwają lub przechodzą stertę w dowolnej kolejności, najwygodniejszej.

To zastrzeżenie wydaje się również mieć zastosowanie do .head, ale .dequeue zwraca elementy w kolejności.

Domyślna kolejność jest malejący (od najwyższego priorytetu wychodzi pierwszy), ale można wyraźnie zdać odwrotnej kolejności przy konstruowaniu:

val normalOrder = implicitly[Ordering[(Int, String)]] 
val reversedOrder = Ordering.reverse(normalOrder) 
val pq = scala.collection.mutable.PriorityQueue[(Int, String)](reversedOrder) 

Answer 3

Jeśli wszystkie potrzebne jest odwrócenie niejawny zamawiania, można po prostu Odwróć kolejkę od razu:

val pq = PriorityQueue.empty[(Int, String)].reverse