ejemplo - priority queue java
¿Hay una lista ordenada indexable en el paquete Java.util? (7)
Considere la List combinada con Collections.sort() .
Estoy buscando una estructura de datos en el paquete java.util. Lo necesito para cumplir con los siguientes requisitos:
- El número de elementos es (teóricamente) ilimitado.
- Los elementos se ordenan en orden ascendente.
- Puede obtener el elemento nth (rápido).
- Puede eliminar el elemento n (rápido).
Esperaba encontrar una lista de saltos indexables, pero no lo hice. ¿Tienen alguna estructura de datos que cumpla con los requisitos que he establecido?
Esta pregunta es muy similar a
Echa un vistazo a mi respuesta a esa pregunta .
Básicamente sugiere lo siguiente:
class SortedArrayList<T> extends ArrayList<T> {
@SuppressWarnings("unchecked")
public void insertSorted(T value) {
add(value);
Comparable<T> cmp = (Comparable<T>) value;
for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--) {
T tmp = get(i);
set(i, get(i-1));
set(i-1, tmp);
}
}
}
Una nota sobre su primer requisito: " El número de elementos es ilimitado ".
Es posible que desee restringir esto a algo como "La cantidad de elementos no debe estar limitada por menos de 2 31 -1 ..." ya que de lo contrario, está descartando todas las opciones respaldadas por una matriz Java. (Podría salirse con un número arbitrario de elementos utilizando, por ejemplo, una lista enlazada, pero no puedo ver cómo podría hacer búsquedas rápidas en eso).
Mira a PriorityQueue .
Si no necesita elementos similares en su estructura de datos, el TreeSet habitual también se ajusta a sus requisitos.
No existe una estructura de datos simple que cumpla con todos sus criterios.
El único que sé que cumple todos ellos sería una lista de salto indexable . Sin embargo, no conozco ninguna implementación de Java fácilmente disponible.
No hay tal contenedor en las bibliotecas estándar de Java.
Cuando necesito una estructura de datos con estas propiedades, uso una implementación de List (generalmente una ArrayList , pero no importa), y hago todas las inserciones usando Collections.binarySearch .
Si tuviera que encapsular una lista ordenada como una clase reutilizable, implementaría la interfaz de la Lista, delegando todos los métodos a una implementación de Lista ''estándar'' (incluso se puede pasar como un parámetro al constructor). Implementaría cada método de inserción (agregar, agregar Todo, establecer, eliminar Iterator) lanzando una excepción ( UnsupportedOperationException ), para que nadie pueda romper la propiedad "siempre ordenada". Finalmente, proporcionaría un método insertSorted que usaría Collections.binarySearch para hacer la inserción.
Siguiendo con lo establecido por dwb con List<T> y Collections.sort() , puede usar ArrayList<T> como implementa List<T> (y no está sincronizado como Vector<T> menos que desee esa sobrecarga). Esa es probablemente tu mejor apuesta porque (Sun) normalmente investigan mucho en estas áreas (por lo que he visto de todos modos). Si necesita ordenar por algo que no sea el "predeterminado" (es decir, no está ordenando una lista de enteros, etc.), proporcione su propio comparador.
EDITAR: Lo único que no cumple con sus requisitos son las eliminaciones rápidas ...
TreeSet proporciona la funcionalidad de clasificación natural al tiempo que agrega elementos a la lista. Pero si no necesita esto y está permitido Collections.sort () puede usar ArrayList simple.