¿Cómo puedo realizar un seguimiento eficiente del elemento más pequeño de una colección?

Question

En la vena de preguntas de programación:supongamos que hay una colección de objetos que se pueden comparar entre sí y clasificar.¿Cuál es la forma más eficaz de realizar un seguimiento del elemento más pequeño de la colección a medida que se agregan objetos y ocasionalmente se elimina el más pequeño actual?

Answer 1

Usar un montón mínimo es la mejor manera.

http://en.wikipedia.org/wiki/Heap_(data_structure)

Está hecho a medida para esta aplicación.

Answer 2

Si necesita inserción y eliminación aleatorias, la mejor manera probablemente sea una matriz ordenada.Las inserciones y eliminaciones deben ser O(log(n)).

Answer 3

@harpreet
Eso no es óptimo.Cuando se elimina un objeto, erickson tendrá que escanear toda la colección para encontrar el nuevo más pequeño.

Quieres leer sobre Árbol de búsqueda binaria's.MS tiene una buena sitio para iniciar el camino.Pero quizás quieras conseguir un libro como Introducción a los algoritmos (Cormen, Leiserson, Rivest, Stein) si quieres profundizar.

Answer 4

Para elimina ocasionalmente un Montón de Fibonacci Es incluso más rápido que el montón mínimo.La inserción es O (1) y encontrar el mínimo también es O (1).La eliminación es O(log(n))

Answer 5

Si necesita inserto y eliminación aleatorios, la mejor manera es probablemente una matriz ordenada.Las inserciones y las eliminaciones deben ser o (log (n)).

Sí, pero deberá volver a ordenar cada inserción y (tal vez) cada eliminación, que, como usted indicó, es O(log(n)).

Con la solución propuesta por Harpreet:

• tienes una pasada O(n) al principio para encontrar el elemento más pequeño
• las inserciones son O(1) a partir de entonces (solo se necesita 1 comparación con el elemento más pequeño ya conocido)
• las eliminaciones serán O(n) porque necesitará volver a encontrar el elemento más pequeño (tenga en cuenta que la notación O grande es el peor de los casos).También puede optimizar verificando si el elemento que se va a eliminar es el más pequeño (conocido) y, si no, simplemente no vuelva a realizar ninguna verificación para encontrar el elemento más pequeño.

Entonces depende.Uno de estos algoritmos será mejor para un caso de uso con muchas inserciones y pocas eliminaciones, pero el otro es, en general, más consistente.Creo que utilizaría de forma predeterminada el mecanismo de Harpreet a menos que supiera que el número más pequeño se eliminaría con frecuencia, porque eso expone un punto débil en ese algoritmo.

Answer 6

Harpreet:

las inserciones en eso serían lineales ya que hay que mover elementos para una inserción.

¿No depende eso de la implementación de la colección?Si actúa como una lista enlazada, las inserciones serían O(1), mientras que si se implementara como una matriz sería lineal, como usted indicó.

Answer 7

Depende de qué operaciones necesite que admita su contenedor.A montón mínimo es lo mejor si necesita eliminar el elemento min en un momento dado, aunque varias operaciones no son triviales (tiempo log(n) amortizado en algunos casos).

Sin embargo, si solo necesita empujar/hacer estallar desde el frente/detrás, puede usar un mindeque que logra un tiempo constante amortizado para todas las operaciones (incluido findmin).Tu puedes hacer una búsqueda en academic.google.com para aprender más sobre esta estructura.Un amigo y yo colaboramos recientemente para lograr también una versión de mindeque mucho más fácil de entender e implementar.Si esto es lo que estás buscando, podría publicarte los detalles.