Come restituire l'elemento kth in TreeSet in Java

Question

Forse non sto utilizzando la giusta struttura dati. Ho bisogno di usare un set, ma voglio anche restituire in modo efficiente il kth elemento più piccolo. TreeSet può fare java? Non sembra esistere alcun metodo incorporato di TreeSet per farlo.

Per favore aiutatemi.

Answer 1

Usa TreeSet.iterator() per ottenere un iteratore in ordine crescente e chiamare next() K volte:

// Example for Integers 
Iterator<Integer> it = treeSet.iterator(); 
int i = 0; 
Integer current = null; 
while(it.hasNext() && i < k) { 
    current = it.next(); 
    i++; 
} 

Answer 2

Hai solo bisogno di scorrere all'elemento k. Un modo per farlo sarebbe quello di utilizzare uno dei Iterables.get metodi Guava s':

T element = Iterables.get(set, k); 

Non c'è costruito nel metodo per fare questo perché un Set non è un List e basati su indici operazioni del genere sono generalmente i riservati per List s. Un TreeSet è più appropriato per cose come trovare l'elemento contenuto più vicino che è> = un certo valore.

Una cosa che si potrebbe fare se il più veloce possibile l'accesso al più piccolo elemento KTH erano davvero importante sarebbe quella di utilizzare un ArrayList piuttosto che un TreeSet e gestire gli inserti di ricerca binaria per il punto di inserimento e sia inserendo l'elemento in quell'indice o sostituendo l'elemento esistente in quell'indice, a seconda del risultato della ricerca. Quindi è possibile ottenere il k più piccolo elemento in O (1) chiamando semplicemente get(k).

Si potrebbe anche creare un'implementazione di SortedSet che gestisce tutto ciò e aggiunge il metodo get(index) se si desidera davvero.

Answer 3

Non credo che TreeSet abbia un metodo che esegue direttamente questo. Esistono alberi di ricerca binaria che supportano l'accesso casuale O (log n) (a volte sono chiamati alberi di statistica ) e sono disponibili Java implementations of this data structure. Queste strutture vengono in genere implementate come alberi di ricerca binari che memorizzano le informazioni in ciascun nodo contando quanti elementi si trovano a sinistra oa destra del nodo, quindi è possibile effettuare una ricerca lungo l'albero per trovare l'elemento appropriato discendendo nella sottostruttura appropriata a ogni passo. Il classico libro "Introduzione agli algoritmi, terza edizione" di Cormen, Rivest, Leisserson e Stein esplora questa struttura di dati nel loro capitolo "Aumentare le strutture dati" se sei curioso di implementarne uno tu stesso.

In alternativa, è possibile (in alcuni casi) utilizzare il metodo tailSetTreeSet e una ricerca binaria modificata per provare a trovare l'elemento kth. Nello specifico, guarda il primo e l'ultimo elemento dello TreeSet, poi (se possibile dato il contenuto) scegli qualche elemento che è a metà strada tra i due e passalo come argomento a tailSet per ottenere una vista degli elementi del set dopo il punto medio. Utilizzando il numero di elementi nello tailSet, puoi decidere se hai trovato l'elemento o se esplorare le metà sinistra o destra dell'albero. Si tratta di un interpolation search leggermente modificato sull'albero e potrebbe potenzialmente essere veloce. Tuttavia, non conosco la complessità interna dei metodi tailSet, quindi potrebbe essere effettivamente peggio dell'albero della statistica degli ordini. Potrebbe anche non riuscire se non è possibile calcolare il "punto medio" di due elementi, ad esempio, se si memorizzano String s nello TreeSet.

Spero che questo aiuti!

Answer 4

[Qui di seguito, ho abbreviate "kth più piccola operazione elemento di ricerca" come "Kth op."]

È necessario dare ulteriori dettagli. Quali operazioni fornirà la struttura dati? è K in Kth operazione molto piccola rispetto a N o può essere qualcosa? Con quale frequenza si avranno inserimenti & cancellazioni rispetto alle ricerche? Quante volte hai Kth la ricerca di elementi più piccola rispetto alle ricerche? Stai cercando una soluzione rapida di un paio di linee all'interno della libreria Java o sei disposto a spendere qualche sforzo per creare una struttura dati personalizzata?

Le operazioni per fornire potrebbe essere qualsiasi sottoinsieme di:

• LookUp (trovare un elemento con la sua chiave, dove la chiave è paragonabile e può essere qualsiasi cosa)

• Inserire

• Elimina

• Kth

Ecco alcune possibilità:

• Se non ci saranno/poche inserzioni molto & eliminazioni, si può solo ordinare i elementi e utilizzare un array, con O (Log (N)) tempo di ricerca e O (1) per K.

• Se O (log (N)) per LookUp, Inserire, Elimina e O (k) per Kth op. è abbastanza buono, probabilmente l'implementazione più semplice sarebbe Skip List. (Articolo di Wikipedia è molto buona se avete bisogno di maggiori dettagli)

• Se K è abbastanza piccolo, o Kth operazioni arriverà solo dopo "inserimenti & eliminazioni fase" è possibile mantenere i più piccoli K elementi in un heap, ordinamento dopo gli inserimenti & eliminazioni per O (N + k Log k) tempo.(Avrete anche bisogno di un hash separato per LookUp)

• Se K è arbitraria e O (N) è abbastanza buono per Kth operazione, è possibile utilizzare un hash per O (1) Ricerca temporale e uso dell'algoritmo "One-sided-QuickSort" per le operazioni Kth (l'idea di base è fare un ordinamento rapido, ma su ogni divisione binaria recurse solo sul lato di cui hai realmente bisogno, che darebbe (questo è una grossolana semplificazione) N (1/2 + 1/4 + 1/8 + ...) = O (N) tempo previsto)

• È possibile costruire un "semplice" struttura Interval Tree Augmented con ogni nodo mantenendo il numero dei suoi figli, in modo che LookUp, Inserire, Elimina, Kth tutti calcolo in O (log N) tempo fino a quando l'albero è bilanciato, ma forse non sarebbe difficile da implementare se sei un principiante.

ecc. Ecc. L'insieme di alternative è infinito come le possibili interpretazioni della tua domanda.

Answer 5

È possibile utilizzare un ConcurrentSkipListSet e utilizzare il metodo toArray()? ConcurrentSkipListSet è ordinato in base all'ordine naturale degli elementi. L'unica cosa di cui non sono sicuro è se toArray() è O (n) o dato che è supportato da un List (supportato da un array, come ArrayList) è O (1).

Se toArray() è O (1), dovresti essere in grado di essere un skipList.toArray() [k] per ottenere l'elemento k-th più piccolo.

Answer 6

Ho avuto lo stesso problema. Così ho preso il codice sorgente di java.util.TreeMap e ho scritto IndexedTreeMap. Implementa il mio IndexedNavigableMap:

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> { 
    K exactKey(int index); 
    Entry<K, V> exactEntry(int index); 
    int keyIndex(K k); 
} 

L'implementazione è basata sull'aggiornamento pesi nodo nell'albero rosso-nero quando viene cambiata. Il peso è il numero di nodi figli sotto un dato nodo, più uno solo. Per esempio, quando un albero viene ruotato verso sinistra:

private void rotateLeft(Entry<K, V> p) { 
    if (p != null) { 
     Entry<K, V> r = p.right; 

     int delta = getWeight(r.left) - getWeight(p.right); 
     p.right = r.left; 
     p.updateWeight(delta); 

     if (r.left != null) { 
      r.left.parent = p; 
     } 

     r.parent = p.parent; 


     if (p.parent == null) { 
      root = r; 
     } else if (p.parent.left == p) { 
      delta = getWeight(r) - getWeight(p.parent.left); 
      p.parent.left = r; 
      p.parent.updateWeight(delta); 
     } else { 
      delta = getWeight(r) - getWeight(p.parent.right); 
      p.parent.right = r; 
      p.parent.updateWeight(delta); 
     } 

     delta = getWeight(p) - getWeight(r.left); 
     r.left = p; 
     r.updateWeight(delta); 

     p.parent = r; 
    } 
    } 

updateWeight aggiorna semplicemente pesi fino alla radice:

void updateWeight(int delta) { 
     weight += delta; 
     Entry<K, V> p = parent; 
     while (p != null) { 
      p.weight += delta; 
      p = p.parent; 
     } 
    } 

E quando abbiamo bisogno di trovare l'elemento in base all'indice qui è l'implementazione che usi pesi:

public K exactKey(int index) { 
    if (index < 0 || index > size() - 1) { 
     throw new ArrayIndexOutOfBoundsException(); 
    } 
    return getExactKey(root, index); 
} 

private K getExactKey(Entry<K, V> e, int index) { 
    if (e.left == null && index == 0) { 
     return e.key; 
    } 
    if (e.left == null && e.right == null) { 
     return e.key; 
    } 
    if (e.left != null && e.left.weight > index) { 
     return getExactKey(e.left, index); 
    } 
    if (e.left != null && e.left.weight == index) { 
     return e.key; 
    } 
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1); 
} 

disponibile anche molto utile trovare l'indice di un tasto:

public int keyIndex(K key) { 
    if (key == null) { 
     throw new NullPointerException(); 
    } 
    Entry<K, V> e = getEntry(key); 
    if (e == null) { 
     throw new NullPointerException(); 
    } 
    if (e == root) { 
     return getWeight(e) - getWeight(e.right) - 1;//index to return 
    } 
    int index = 0; 
    int cmp; 
    if (e.left != null) { 
     index += getWeight(e.left); 
    } 
    Entry<K, V> p = e.parent; 
    // split comparator and comparable paths 
    Comparator<? super K> cpr = comparator; 
    if (cpr != null) { 
     while (p != null) { 
      cmp = cpr.compare(key, p.key); 
      if (cmp > 0) { 
       index += getWeight(p.left) + 1; 
      } 
      p = p.parent; 
     } 
    } else { 
     Comparable<? super K> k = (Comparable<? super K>) key; 
     while (p != null) { 
      if (k.compareTo(p.key) > 0) { 
       index += getWeight(p.left) + 1; 
      } 
      p = p.parent; 
     } 
    } 
    return index; 
} 

È possibile trovare il risultato di questo lavoro allo http://code.google.com/p/indexed-tree-map/. Spostato su https://github.com/geniot/indexed-tree-map

Answer 7

So che questa domanda è piuttosto vecchia, ma poiché TreeSet implementa NavigableSet si ha accesso al metodo subSet che viene eseguito in tempo costante.

subSet(k, k + 1).first(); 

La prima chiamata() richiede log (n) l'ora in cui n è la dimensione del set originale. Ciò crea alcuni oggetti non necessari che potrebbero essere evitati con un'implementazione più robusta di TreeSet, ma evita l'uso di una libreria di terze parti.