Diferencia entre un montón y una cola de prioridad

36

Siempre pensé que montones y colas de prioridad son sinónimos - una estructura de datos abstracta que los soportes insert, findMiny deleteMinlas operaciones.

Alguna literatura parece estar de acuerdo conmigo - Chris Okasaki es puramente funcional Estructuras de datos (capítulo 3), por ejemplo.

Por otro lado, la Wikipedia montón página define como una estructura de datos basada en el árbol, y los estados que son montones una aplicación concreta de colas de prioridades.

Estoy teniendo un duro conciliar esto con el hecho de que se me ocurre aplicación más de un montón - montones de izquierda, montones binomiales, montones splay ...

¿El simple hecho de que una pila puede ser implementado con diferentes estructuras de datos no significa, por definición, que es una estructura de datos abstracta? Y si ese es el caso, ¿existe una diferencia real con colas de prioridad?

data-structures Nicolas Rinaudo
fuente
11
Lea la página de Wikipedia sobre colas de prioridad ( en.wikipedia.org/wiki/Priority_queue ), que dice "una cola de prioridad puede ser implementado con un montón o una variedad de otros métodos, como una matriz no ordenada" - y que en realidad es la respuesta a tu pregunta.
Doc Brown
2
Bueno, en realidad no, no me ayuda a entender si un montón es una estructura de datos concreta o una estructura abstracta. Tiendo a decir uno abstracto, ya que hay muchas implementaciones concretas de un montón. Si ese es el caso, y una lista de prioridades y un montón son estructuras de datos abstractas con las mismas propiedades, entonces necesito ayuda para comprender la diferencia, y decir que una es una posible implementación de la otra no es muy útil si ninguna de las dos es realmente una Implementación concreta.
Nicolas Rinaudo
Las cosas son aún peores: un montón binario se puede implementar como una matriz o como un árbol binario. Afortunadamente, aún no he oído hablar de una matriz implementada como algo más.
Alexey

Respuestas:

25

Una cola prioritaria puede tener cualquier implementación, como una matriz que busca linealmente cuando aparece. Todo lo que significa es que cuando aparece, obtiene el valor con el mínimo o el máximo dependiendo.

Un montón clásico, como se le suele denominar, suele ser un montón mínimo. Una implementación que tiene una buena complejidad de tiempo ( O(log n)en push y pop) y sin sobrecarga de memoria.

monstruo de trinquete
fuente
44
¿Quiere decir que la diferencia es que si bien comparten las mismas operaciones ( findMin, deleteMin, insert"buenas" complejidades), montones han garantizados por ellos, donde las colas de prioridad no lo hacen?
Nicolas Rinaudo
¿No puede el montón también tener diferentes implementaciones con diferentes complejidades de tiempo (un árbol binario vinculado habitual, por ejemplo)? Además, la complejidad del tiempo depende de la memoria utilizada. Si se trata de una cinta magnética O(log(n)), supongo que no habrá push and pop.
Alexey
6

Este sitio web ofrece una explicación muy clara. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

En resumen, se puede implementar una cola prioritaria utilizando muchas de las estructuras de datos que ya hemos estudiado (una matriz, una lista vinculada o un árbol de búsqueda binario). Sin embargo, esas estructuras de datos no proporcionan las operaciones más eficientes. Para que todas las operaciones sean muy eficientes, utilizaremos una nueva estructura de datos llamada montón.

Chihung Yu
fuente
1
Tenga en cuenta que en el resumen de la página a la que se vinculó, la cola de prioridad en sí misma se denomina estructura de datos .
Alexey
2

Creo que lo que escribiste sobre concreto versus abstracto es correcto. Sin embargo, cuando dices que los montones extendidos, los montones binomiales son implementaciones diferentes de montones, creo que es más correcto decir que son diferentes tipos de montones. Heap me parece una categoría de implementación que generalmente garantiza no solo la misma interfaz, sino también los mismos tiempos de acceso.

Puede ver esto con mapas asociativos, tablas de hash y árboles de búsqueda binarios también. Las tablas Bsts y hash son estructuras de datos concretas que proporcionan la interfaz abstracta de mapa asociativo. Los árboles negros y rojos y los árboles AVL son bsts equilibrados, con las mismas grandes garantías de O y la misma interfaz adicional (en orden transversal). Son diferentes tipos de árboles, diría que más que diferentes implementaciones de árboles. Son implementaciones diferentes pero estrechamente relacionadas de mapas asociativos.

Nir Friedman
fuente