val maxHeap = scala.collection.mutable.PriorityQueue[Int] //Gives MaxHeap
Qual è il modo più conciso ed efficace per utilizzare Ordering per trasformare PriorityQueue in un minHeap?Qual è il modo più semplice ed efficace per creare un heap minimo in Scala?
Dovrete definire il proprio Ordering:
scala> object MinOrder extends Ordering[Int] {
def compare(x:Int, y:Int) = y compare x
}
defined object MinOrder
quindi utilizzare tale durante la creazione del mucchio:
scala> val minHeap = scala.collection.mutable.PriorityQueue.empty(MinOrder)
minHeap: scala.collection.mutable.PriorityQueue[Int] = PriorityQueue()
scala> minHeap.ord
res1: Ordering[Int] = [email protected]
Penso che non sia nemmeno necessario creare il proprio ordinamento, è possibile utilizzare il metodo .reverso di uno già esistente: Ordine [Int] .reverso – nachinius
per il completamento val minHeap = scala.collection.mutable.PriorityQueue.empty (Ordinazione [Int] .reverse) https://codebunk.com/pb/788100787 – nachinius
Aggiornamento agosto 2016: si può considerare la proposta chrisokasaki/scads/scala/heapTraits.scala da Chris Okasaki (chrisokasaki).
Tale proposta illustra la parte "non-così-facile" di un Heap:
Proof of concept per cumuli typesafe con un'operazione di unione.
Qui, "typesafe" significa che l'interfaccia non consentirà mai di mescolare diversi ordini nello stesso heap.
In particolare,
- quando si aggiunge un elemento ad un mucchio esistente, che l'inserimento non può comportare un ordinamento diverso da quello utilizzato per creare il mucchio esistente e
- durante l'unione di due cumuli esistenti, i cumuli sono garantito di essere stato creato con lo stesso ordine.
Vedi its design.
val h1 = LeftistHeap.Min.empty[Int] // an empty min-heap of integers
Solo per riferimento futuro, molto spesso "più semplice" e "più efficiente" si escludono a vicenda. –