La coda di priorità ordinata Scala ha sempre il numero più basso come testa, ordine crescente

Question

Vorrei ottenere un esempio di codice che compia l'ordine crescente di elementi in una coda di priorità.

Desidero memorizzare Tuple2(Int, String) all'interno di una coda di priorità in modo che sia ordinato dal primo elemento della tupla in ordine crescente. Se la mia coda di priorità è chiamata pq e chiamo pq.head vorrei ottenere la tupla con il numero più basso, stessa cosa con la chiamata 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)) 

Come applicare l'ordine crescente al primo elemento al momento dell'inserimento sopra?

Grazie

Answer 1

PriorityQueue.apply e PriorityQueue.empty entrambi prendono una Ordering un'istanza implicito che verrà utilizzato per ordinare il contenuto-testa sarà il valore "più" secondo tale ordinamento. Stai diventando quello predefinito per le tuple, che è un ordinamento lessicografico sugli elementi della tupla, che non è quello che vuoi, dal momento che renderà la tupla con il primo elemento più grande della testa.

Ci sono un paio di modi per risolvere questo problema. Il modo più semplice è solo chiamare .reverse sulla tua coda, che ti darà una nuova coda con lo stesso contenuto ma l'ordine opposto, il che significa che la tupla con il valore più basso sarà la testa.

È inoltre possibile fornire il proprio ordinamento quando si crea la coda:

import scala.collection.mutable.PriorityQueue 

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

O se esplicitamente non si vuole il secondo elemento da consultare:

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

Questo è forse un po ' più efficiente di invertire la coda, ma probabilmente non abbastanza da preoccupare, quindi dovresti semplicemente scegliere l'approccio che ritieni più elegante.

Answer 2

Dal scaladoc:

Solo le dequeue e dequeueAll metodi saranno metodi in ordine di priorità di ritorno (durante la rimozione elementi dal mucchio). I metodi di raccolta standard, tra cui drop e iterator, rimuoveranno o attraverseranno l'heap in qualsiasi ordine sembra più conveniente.

Questo avvertimento sembra valere anche per .head, ma .dequeue restituisce gli elementi in ordine.

L'ordinamento di default è discendente (dal momento che la massima priorità viene fuori prima), ma è possibile passare in modo esplicito un ordine inverso durante la costruzione:

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

Answer 3

Se tutto ciò che serve è invertire l'ordine implicita, si può solo invertire subito la coda:

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