Estructura de datos ordenada de manera eficiente que admite claves duplicadas

Question

Estoy buscando una estructura de datos que ordene objetos en la inserción de manera eficiente. Me gustaría ordenar estos objetos (en este caso, individuos) en función del valor de una variable particular (en este caso, la aptitud).

La estructura de datos debe permitir claves duplicadas ya que un valor de condición física particular puede ocurrir en diferentes individuos. Esto es un problema porque, por ejemplo, la estructura de datos de TreeMap no permite duplicar claves. Preferiría usar este tipo de estructura tipo árbol debido a su eficiencia O (log N).

Si inserto las personas en una lista ordenada, la eficiencia bajaría a O (n), y la clasificación de las personas después de que se han insertado tampoco sería muy eficiente.

¿Existe una estructura de datos que sea eficiente, mantenga a las personas ordenadas y admita duplicados?

Voy a agregar y eliminar entradas con mucha frecuencia después de que se haya creado la estructura de datos, por lo que ordenar los objetos una vez creada la estructura sería muy costoso.

Answer 1

Tanto Apache Commons como Guava soportan multiprops, que es lo que está buscando.

Alternativamente, dependiendo de su caso de uso, usted podría reunir los elementos de una ArrayList y ordenarla después en O (n lg n) tiempo total.

O bien, podría definir una comparación que verifique primero la aptitud física y otras propiedades distintivas de los artículos si las condiciones físicas son iguales.

Answer 2

Si solo le importa el pedido una vez que se han agregado todas las personas, y no agrega ningún individuo nuevo después, entonces ordenar una ArrayList es probablemente la opción más rápida.

De lo contrario, puede usar un TreeSet, y tener un comparador que compare primero por estado físico, y luego por identity hash code si las condiciones son iguales (o por cualquier otra propiedad distinta). Por lo tanto, todos tus objetos serán diferentes, pero se ordenarán por estado físico.

Answer 3

En informática clásica, la estructura de datos que está buscando se llama Priority Queue.

Sucede que desde java 1.5, la biblioteca de clase java estándar tiene una implementación: java.util.PriorityQueue.

Lo usaría.

Answer 4

Si desea utilizar un TreeMap normal, puede hacerlo almacenar contenedores de valores en lugar de los valores propios. Estas envolturas almacenarían múltiples con la misma clave.

De lo contrario, podría usar algún tipo de estructura de lista ordenada, basada en un árbol de búsqueda binaria. Hace un tiempo escribí uno que está disponible aquí: http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/, pero estoy seguro de que existen más implementaciones estándar. La ventaja de este tipo de estructura es que el método contains(Object) se ejecuta en tiempo logarítmico en lugar de lineal.