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.
¿Cuántos artículos? ¿Se persisten en alguna parte? Si es así, ¿cómo? – Lazarus
Diga más acerca de qué tan eficiente desea que sean * insertion *, * retrieval * (de elementos prioritarios) y * removal *, relativos entre sí. – Artelius
Me gustaría calificar primero los artículos y luego recuperar los primeros x mejores artículos en el orden correcto. Entonces, como hay muchas inserciones, la inserción debería ser bastante eficiente. La recuperación podría ser menos eficiente. – ladi