Lista de prioridades eficiente

Question

Estoy buscando una estructura de datos eficiente para representar una lista de prioridades. Específicamente, debo asignar una prioridad a un conjunto de ítems y devolver solo los ítems de mayor puntuación. He analizado las colas de prioridad que operan en montones, pero no parecen realmente satisfacer mis necesidades. Reorganizarán la estructura del montón tan pronto como sondearé el elemento de calificación superior de la cola.

La solución más simple sería, por supuesto, una lista vinculada, que en el peor de los casos llevaría bastante tiempo para la operación de inserción.

¿Alguien tiene una mejor solución?

Answer 1

Los montones parecen muy adecuados, y parece que lo estás haciendo mal.

di que quieres los elementos primeras X (¿cómo afecta esto a comparar x n, por cierto?)

Lo que está haciendo es poner todo en un máximo de heap y conseguir la x superior.

Sugiero en su lugar, utiliza un min-montón de exactamente x elementos.

Primero x elementos que inserta en el montón.

Próximo elemento entrante, se compara con el min que se puede hacer muy rápidamente (O (1) vez) en el montón. Si es más pequeño, simplemente ignora el elemento entrante.

Si el elemento entrante es mayor que min, entonces aumenta el mínimo al elemento entrante y lo baja en el montón. Esto debería ser logx time en el peor.

Una vez hecho esto (en tiempo nlogx), puede recuperar los elementos del montón en orden ordenado en el tiempo O (xlogx).

Dependiendo de cómo sean sus datos (y cuán pequeña es x), usar esta solución de almacenamiento mínimo puede ser realmente rápido.

---

Si realmente quieren realmente los insertos para ser súper rápido y no les importa mucho acerca de la recuperación, entonces también puede hacer lo siguiente.

Inserte los elementos en un vector (matriz con tiempo de inserción de O (1) amortizado) en el orden en que aparecen.

El uso del algoritmo de selección para encontrar el elemento más grande x (en tiempo O (n), pero las constantes pueden ser grandes). Dicen que el número es S.

Ahora recorrer la matriz comparando cada elemento con S y seleccionar las que tan grandes como S.

Si x es de tamaño razonable y comparable a n (como n/2 o algo así) este podría funcionar bien, pero si x es pequeño en comparación con n, sugeriría ir con el min-montón.

Answer 2

Hmm. Skip lists? Deben tener inserción O (log n) (como cola basada en el montón) pero el elemento superior debe ser O (1) [incluso eliminarlo]. Incluso podrían implementarse utilizando algoritmo sin bloqueo.

Answer 3

El JDK tiene una clase incorporada pqueue (java.util.PriorityQueue) que se basa en un algoritmo de montón.

Disculpa, acabo de ver un poco acerca de montones que no se ajustan a tus necesidades. ¿Puedes explicar porque? Puede escribir un comparador personalizado (o hacer que sus artículos sean comparables) y PriorityQueue ordenará sus artículos de manera adecuada.

Answer 4

Si sólo necesita las k artículos de primera y Nunca necesidad de mirar a los demás, se puede utilizar una simple lista vinculada o matriz almacenar sólo los actuales superiores k artículos, más un número (el peor puntaje de los elementos en la lista).

En la operación Add(), simplemente compare el artículo con el peor valor de la lista y, si es mejor, cambie el peor con el elemento agregado. Esto toma O (k) vez en el peor caso para la inserción porque necesita encontrar el elemento que tiene actualmente la peor puntuación. El caso promedio, sin embargo, es O (1), ya que, a medida que agrega mejores elementos a la lista, la probabilidad de tener que hacer un intercambio tiende a 0 (es decir, en realidad no está agregando ningún elemento) .

Por lo tanto, si genera elementos al azar, es probable que su rendimiento sea muy bueno. Incluso si genera artículos ordenados (en el peor de los casos), podría ser lo suficientemente rápido para su valor de k.