Scala's TreeSet vs TreeSet di Java - sondaggio?

Question

Se desidero rimuovere la voce più alta nel tempo log(n) in Java TreeSet, io uso treeSet.pollFirst() - qual è l'equivalente per la classe mutable.TreeSet di Scala?

In ogni caso, ciò che voglio veramente è una struttura di dati di coda con priorità di heap che mi consente di usare removeMax, add e updatePriority in tempo logaritmico. Ho guardato la libreria delle collezioni Scala e sono confuso - mentre lo mutable.PriorityQueue mi lascia deque (ovvero removeMax) in tempo logaritmico - non fornisce alcun modo per aggiornare la priorità nel tempo di registrazione (dovrei scansionare e rimuovere la voce e aggiungere nuovamente tempo lineare). Allo stesso modo mutable.TreeSet mi consentirebbe di aggiornare la priorità in tempo logaritmico (cancellando e riaggiustando in modo ritmato) ma non ha un'operazione removeMax (cioè pollFirst). Quale contenitore di collezioni dovrei usare? Per favore non mi riferire a dipendenze esterne.

Answer 1

È possibile utilizzare i metodi head e last nello immutable.TreeSet, che sono O(log n). Gli stessi metodi esistono in mutable.TreeSet, ma non sono stati sovrascritti per fornire una migliore efficienza e tempo ammortizzato (in Scala 2.10). Il metodo head sarà logaritmico, ma potrebbe istanziare un iteratore quando lo si fa. Il metodo last lo attraverserà effettivamente, con complessità lineare. La buona notizia è che puoi controllare ciò che è più piccolo o più grande con una Ordering personalizzata - e ottenerla facilmente da una Ordering esistente chiamando lo Ordering.reverse.

Se è necessario rimuovere tale elemento, utilizzare semplicemente -=. È possibile creare la propria classe di valore implicita per gestire il metodo pollFirst nel set di strutture.

implicit class MyExtensions[T](ts: mutable.TreeSet[T]) extends AnyVal { 
    def pollFirst(): T = { 
    val elem = ts.head 
    ts -= elem 
    elem 
    } 
} 

Answer 2

Non una risposta, solo un suggerimento :) ricorda che è possibile accedere a librerie Java da Scala (beh, se si compila alla JVM :) quindi se TreeSet di Java funziona per voi, usarlo :)

Puoi anche chiarire le tue esigenze; quali sarebbero i parametri del tuo metodo updatePriority? la cui priorità si sta tentando di aggiornare?