framework - Cómo devolver el elemento kth en TreeSet en Java

ejercicios resueltos de colecciones en java

Question

Tal vez no estoy usando la estructura de datos correcta. Necesito usar un conjunto, pero también quiero devolver eficientemente el k-ésimo elemento más pequeño. ¿Puede TreeSet en java hacer esto? Parece que no hay un método incorporado de TreeSet para hacer esto.

Por favor, ayúdame.

Answer 1

¿Podría usar un ConcurrentSkipListSet y usar el método toArray ()? ConcurrentSkipListSet está ordenado por el orden natural de los elementos. Lo único de lo que no estoy seguro es si el toArray () es O (n) o si está respaldado por una lista (respaldado por una matriz, como ArrayList) es O (1).

Si toArray () es O (1), usted debería poder ser un skipList.toArray () [k] para obtener el k-ésimo elemento más pequeño.

Answer 2

No creo que TreeSet tenga un método que lo haga directamente. Hay árboles de búsqueda binarios que sí admiten el acceso aleatorio O (log n) (a veces se denominan árboles de estadísticas de orden ), y hay implementaciones de Java de esta estructura de datos disponibles. Estas estructuras se implementan típicamente como árboles de búsqueda binarios que almacenan información en cada nodo contando cuántos elementos hay a la izquierda o a la derecha del nodo, de modo que se puede realizar una búsqueda en el árbol para encontrar el elemento apropiado descendiendo al subárbol apropiado en cada paso. El clásico libro "Introducción a los Algoritmos, Tercera Edición" de Cormen, Rivest, Leisserson y Stein explora esta estructura de datos en su capítulo "Aumento de las estructuras de datos" si tiene curiosidad por cómo implementar uno.

Alternativamente, puede (en algunos casos) usar el método tailSet y una búsqueda binaria modificada para tratar de encontrar el elemento kth. Específicamente, mire los primeros y últimos elementos del TreeSet , luego (si es posible dado el contenido) elija algún elemento que esté a medio camino entre los dos y páselo como argumento a tailSet para obtener una vista de los elementos del conjunto después del punto medio. Usando la cantidad de elementos en tailSet , puede decidir si ha encontrado el elemento o si explorará las mitades izquierda o derecha del árbol. Esta es una búsqueda de interpolación ligeramente modificada sobre el árbol, y podría ser potencialmente rápida. Sin embargo, no conozco la complejidad interna de los métodos tailSet , por lo que podría ser peor que el árbol de estadísticas de pedidos. También puede fallar si no puede calcular el "punto medio" de dos elementos, por ejemplo, si está almacenando String en su TreeSet .

¡Espero que esto ayude!

Answer 3

Sé que esta pregunta es bastante antigua, pero como TreeSet implementa NavigableSet, tiene acceso al método subSet, que se ejecuta en tiempo constante.

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

La primera () llamada toma el tiempo de registro (n) donde n es el tamaño del conjunto original. Esto crea algunos objetos innecesarios que podrían evitarse con una implementación más sólida de TreeSet, pero evita usar una biblioteca de terceros.

Answer 4

Solo necesita iterar al elemento k . Una forma de hacerlo sería usar uno de los métodos Iterables.get de Guava :

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

No hay un método incorporado para hacer esto porque un Set no es una List y las operaciones basadas en índices como esa generalmente son las reservadas para las List . Un TreeSet es más apropiado para cosas como encontrar el elemento contenido más cercano que sea> = algún valor.

Una cosa que podría hacer si el acceso más rápido posible al elemento k-ésimo más pequeño fuera realmente importante sería utilizar un ArrayList lugar de un TreeSet y manejar inserciones mediante búsqueda binaria para el punto de inserción e insertar el elemento en ese índice o reemplazar el existente elemento en ese índice, dependiendo del resultado de la búsqueda. Entonces podrías obtener el k-ésimo elemento más pequeño en O (1) simplemente llamando a get(k) .

Incluso podría crear una implementación de SortedSet que maneje todo eso y agregue el método get(index) si realmente lo desea.

Answer 5

Utilice TreeSet.iterator () para obtener un iterador en orden ascendente y llame a next() K veces:

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

Answer 6

Yo tuve el mismo problema. Así que tomé el código fuente de java.util.TreeMap y escribí IndexedTreeMap . Implementa mi propio IndexedNavigableMap :

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

La implementación se basa en actualizar los pesos del nodo en el árbol rojo-negro cuando se cambia. El peso es la cantidad de nodos secundarios debajo de un nodo dado, más uno mismo. Por ejemplo, cuando un árbol se gira hacia la izquierda:

 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 simplemente actualiza los pesos hasta la raíz:

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

Y cuando necesitamos encontrar el elemento por índice, aquí está la implementación que usa ponderaciones:

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);
}

También resulta muy útil encontrar el índice de una clave:

 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;
}

Puede encontrar el resultado de este trabajo en http://code.google.com/p/indexed-tree-map/ . Movido a https://github.com/geniot/indexed-tree-map

Answer 7

[Abajo, abreviando "kth operación de búsqueda de elementos más pequeños" como " Kth op."]

Necesitas dar más detalles. ¿Qué operaciones proporcionará su estructura de datos? ¿La operación K en Kth es muy pequeña en comparación con N , o puede ser algo? ¿Con qué frecuencia tendrá inserciones y eliminaciones en comparación con las búsquedas? ¿Con qué frecuencia tendrá Kth búsqueda de elementos más pequeños en comparación con las búsquedas? ¿Está buscando una solución rápida de un par de líneas dentro de la biblioteca Java, o está dispuesto a dedicar un esfuerzo para construir una estructura de datos personalizada?

Las operaciones a proporcionar podrían ser cualquier subconjunto de:

• LookUp (busca un elemento por su clave, donde la clave es comparable y puede ser cualquier cosa)

• Insertar

• Borrar

• Kth

Aquí hay algunas posibilidades:

• Si no hay / muy pocas inserciones y eliminaciones, puede ordenar los elementos y usar una matriz, con O (Log (N)) tiempo de búsqueda y O (1) para Kth .

• Si O (Log (N)) para LookUp , Insert , Delete y O (k) para Kth op. es lo suficientemente bueno, probablemente la implementación más fácil sería Skip Lists. (El artículo de Wikipedia es muy bueno si necesita más detalles)

• Si K es lo suficientemente pequeño, o las operaciones Kth solo vendrán después de la "fase de inserciones y eliminaciones", puede mantener los elementos K más pequeños en un montón, clasificando después de las inserciones y eliminaciones para el tiempo O (N + k Log k) . (También necesitará un Hash separado para LookUp )

• Si K es arbitrario y O (N) es lo suficientemente bueno para la operación Kth , puede usar un Hash para O (1) búsqueda de tiempo, y usar un algoritmo de "unilateral QuickSort" para las operaciones Kth (la idea básica es hacer una tipo rápido, pero en cada división binaria recursiva solo en el lado que realmente necesita; lo que daría (esto es una simplificación general) N (1/2 + 1/4 + 1/8 + ...) = O (N) esperado hora)

• Puedes construir una estructura de árbol de intervalos "simple" aumentada con cada nodo manteniendo el número de sus hijos, de modo que LookUp , Insert , Delete , Kth calculen en O (Log N) el tiempo siempre que el árbol esté equilibrado, pero tal vez lo haría no será difícil de implementar si eres un principiante.

etc. El conjunto de alternativas es infinito como las posibles interpretaciones de tu pregunta.