¿Por qué dos conceptos diferentes se denominan "montón"?

170

¿Por qué se usa el montón de tiempo de ejecución para la asignación dinámica de memoria en lenguajes de estilo C y la estructura de datos llamada "el montón"? ¿Hay alguna relación?

c++ heap terminology heap-memory Andrey Fedorov
fuente
44
Me preguntaba esto hoy mientras estudiaba las estructuras de datos.
MitMaro el
1
pregunta duplicada? http://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap
timB33
3
Vaya a un diccionario de inglés y cuente la cantidad de entradas en "Ejecutar". ¿Cuántas de las más de 40 entradas se aplican a las computadoras? :)
jmucchiello
2
posible duplicado de ¿Cuál es la relación entre "un" montón y "el" montón?
RCIX
Una publicación relacionada aquí wrt runtime heap utilizado para la asignación dinámica de memoria.
RBT

Respuestas:

77

Donald Knuth dice (The Art of Computer Programming, Third Ed., Vol. 1, p. 435):

Varios autores comenzaron alrededor de 1975 para llamar al grupo de memoria disponible un "montón".

No dice qué autores y no da referencias a ningún artículo específico, pero sí dice que el uso del término "montón" en relación con las colas de prioridad es el sentido tradicional de la palabra.

James McNellis
fuente
11
Pool sería un nombre mejor que el montón.
77
Interesante. Alguien debería preguntarle si recuerda qué autores.
Prof. Falken
27
Wikipedia afirma que es porque en una etapa temprana Lisp utilizó un montón (estructura de datos) para implementar su almacén de memoria. No dice cómo. Su referencia es "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introducción a los algoritmos. MIT Press / McGraw-Hill", que no tengo.
Steve Jessop
2
No tengo ninguna referencia para esto, pero supongo que inicialmente la estructura de datos utilizada para organizar las referencias a bloques de memoria abiertos era un montón mínimo. Parece que sería al menos una forma decente de encontrar rápidamente el bloque de memoria más pequeño que le permita almacenar los datos que estaba tratando de almacenar Actualización: lo que dije suena exactamente como bloques de amigos en.wikipedia.org/wiki/Dynamic_memory_allocation # Buddy% 5Fblocks
Será el
44
@SteveJessop - Comprobando Cormen, Leiserson, Rivest, Stein - 3ra edición (2009) al comienzo del capítulo Heapsort solo dice 'El término "montón" fue originalmente acuñado en el contexto de heapsort, pero desde entonces se ha referido a " almacenamiento recolectado ", como los lenguajes de programación que proporcionan Java y Lisp. Nuestra estructura de datos de almacenamiento dinámico no es almacenamiento recolectado de basura, y siempre que nos refiramos a los montones en este libro, nos referiremos a una estructura de datos en lugar de un aspecto de la recolección de basura ''. CLRS - 2da edición también tiene la misma redacción casi exacta (sin indicación de que Lisp haya usado un montón).
dr jimbob
64

Tienen el mismo nombre pero realmente no son similares (incluso conceptualmente). Un montón de memoria se llama montón de la misma manera que se referiría a una cesta de lavandería como un "montón de ropa". Este nombre se usa para indicar un lugar un tanto desordenado donde la memoria se puede asignar y desasignar a voluntad. La estructura de datos (como señala el enlace de Wikipedia al que hace referencia) es bastante diferente.

Andrew Hare
fuente
8
Sí, creo que ese es el punto en el que basa su pregunta: son diferentes. Entonces, ¿por qué se les llama lo mismo? ¿Existe alguna relación subyacente?
Sean Owen el
9
La forma en que interpreté esta respuesta es "no, no hay una relación subyacente", por lo que responde a la pregunta.
Laurence Gonsalves
Andrew está respondiendo eso. No hay relacion. Sólo una coincidencia. El montón de memoria es más fiel al uso común ya que la memoria se asigna como si fuera un "montón de ropa". Sin embargo, la estructura de datos exigía un mayor alcance de imaginación. Y esto se convierte en un "por qué" bastante más interesante. El nombre proviene del hecho de que los nodos están ordenados por su clave y una clave de nodo primario siempre es> = que su nodo secundario.
Alexandre Bell
66
Definitivamente no están relacionados. Sin embargo, el problema de llamarlo "el montón" es que "la contraparte del montón" - "la pila" - también es una pila real.
dan
1
Sé por qué la estructura de datos del montón se llama montón: porque satisface la propiedad del montón. Pero, ¿por qué se llama así a la propiedad del montón? No tiene sentido para mí, ya que un nombre como "top heavy" sería mucho mejor.
Thomas Eding
31

La colisión de nombres es desafortunada, pero no tan misteriosa. Heap es una palabra pequeña y común que se usa para referirse a una pila, colección, grupo, etc. El uso de la palabra para la estructura de datos precede (estoy bastante seguro) al nombre del grupo de memoria. De hecho, el grupo habría sido una opción mucho mejor para este último, en mi opinión. El montón connota una estructura vertical (como una pila), que se ajusta a la estructura de datos, pero no al conjunto de memoria. No pensamos en un montón de grupo de memoria como jerárquico, mientras que la idea fundamental detrás de la estructura de datos es mantener el elemento más grande en la parte superior del montón (y sub-montones).

La estructura de datos se remonta a mediados de los años 60; amontonar el grupo de memoria, principios de los 70. El término montón (que significa grupo de memoria) fue utilizado al menos ya en 1971 por Wijngaarden en las discusiones sobre Algol.

Posiblemente, el primer uso del montón como estructura de datos se encuentra siete años antes en
Williams, JWJ 1964. "Algoritmo 232 - Heapsort", Comunicaciones del ACM 7 (6): 347-348

IJ Kennedy
fuente
1
Sí, pero un montón también implica desorden y los montones de memoria generalmente están desordenados. El montón de estructura de datos está extremadamente bien ordenado. Entonces, de nuevo, hay una falta de coincidencia igual en sentido contrario según la definición común de montón.
jmucchiello
Siempre se introduce como lo opuesto a stack, lo que debería ser suficiente para explicar el nombre de IMO.
reinierpost
1
No es casualidad: la lista gratuita se puede implementar como una cola prioritaria a través de un montón binomial.
Heath Hunnicutt
2
@jmucchiello: un montón de registros (ver foto ) está bien ordenado y se parece a un árbol. Este es el origen del nombre de la estructura de datos según uno de mis libros de texto de pregrado.
gioele
6

En realidad, leer sobre la forma en que se asigna la memoria (ver Bloques de amigos ) me recuerda un montón de estructuras de datos.

Travelling Tech Guy
fuente
Mi comentario sobre la respuesta de Peter Zhang también es relevante aquí. El sistema de amigos binarios se puede representar como un árbol binario, y también se ve como un montón dinámico válido cuando la "clave" de cada nodo es la memoria total debajo de él (pero estos valores son implícitos y nunca cambian). Ni el algoritmo de asignación ni el de liberación usan operaciones de montón en este árbol binario, por lo que puedo decir.
Eric Dubé
5

En mi opinión, es simplemente un accidente / coincidencia que estas dos cosas completamente no relacionadas tengan el mismo nombre. Es como gráfico y gráfico .

MAK
fuente
Sin embargo, los dos gráficos pueden estar relacionados de alguna manera. Imagínese la gráfica de una función como sigue: El dominio tupla, rango) es un vértice y un borde conecta dos de dichos vértices
2
@Amit: para gráficos continuos que significarían un número infinito de vértices. Esto está bien, pero eso también hace que el concepto de bordes entre los vértices no tenga sentido. En el gráfico de la función f (x) = x * 2, ¿hay un borde entre (0,0) y (1,2)? En caso afirmativo, ¿qué tal (0,0) y (0.5,1)? (0,0) y (0.25,0.5)? No hay forma de tener el concepto de un borde entre vértices, por lo que esto no es realmente un gráfico.
MAK el
5

La estructura de datos de tipo montón se utiliza mediante un algoritmo para encontrar la asignación de memoria disponible. Lo siguiente está extraído de http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html .

Cuando newse invoca, comienza a buscar un bloque de memoria libre que se ajuste al tamaño de su solicitud. Suponiendo que se encuentre dicho bloque de memoria, se marca como reservado y se devuelve un puntero a esa ubicación. Hay varios algoritmos para lograr esto porque se debe hacer un compromiso entre escanear toda la memoria para encontrar el bloque libre más pequeño más grande que el tamaño de su objeto, o devolver el primero donde la memoria necesita encajar. Para mejorar la velocidad de obtener un bloque de memoria, las áreas de memoria libres y reservadas se mantienen en una estructura de datos similar a los árboles binarios llamados montón.

Peng Zhang
fuente
1
Soy extremadamente escéptico de esto, específicamente "... las áreas de memoria libres y reservadas se mantienen en una estructura de datos similar a los árboles binarios llamados un montón". Me parece que el autor está adivinando que hay una conexión, basada en el nombre "montón", y probablemente esté equivocado. ¿Alguien puede confirmar / refutar?
Don Hatch
1
Después de una ligera investigación sobre el sistema Binary Buddy (utilizado en Linux), puede representarse mediante un árbol binario debido a cómo divide los datos. Este árbol binario parece un montón dinámico válido si observa los nodos en términos de memoria total, pero los nodos no se insertan en este árbol binario como lo están en un montón máximo: los nodos se insertan directamente en la hoja más pequeña de memoria libre> = el tamaño solicitado. 1 2 3
Eric Dubé
1

Los términos coloquiales stack stack y heap memory no se usan en el estándar C ++. El estándar utiliza almacenamiento estático, almacenamiento de subprocesos, almacenamiento automático y almacenamiento dinámico.

Se puede encontrar más en la sección Duración de almacenamiento de la norma.

Por lo tanto, desde el punto de vista del lenguaje y la biblioteca estándar, no hay confusión.

R Sahu
fuente
1

P. ¿Qué es un montón? A. Un montón es una colección de objetos colocados uno encima del otro.

Responda a su pregunta: tanto el almacenamiento dinámico de memoria como el almacenamiento binario utilizan el mismo concepto que usted conoce. Los datos se almacenan en forma de un montón en la memoria en el mismo orden en que están escritos en el programa, mientras que el montón binario es una estructura de datos que sigue el mismo concepto de almacenamiento de datos de forma ordenada en forma de un montón (Datos en la parte superior del otro). Déjame saber lo que piensas en la sección de comentarios.

Mayank Tolani
fuente
-2

¿Quizás el primer montón de memoria implementado fue administrado por una estructura de montón?

Adam Maras
fuente
8
Esa hipótesis no parece nada obvia: ¿cómo es útil un montón (la estructura de datos) para mantener un montón (la región de memoria dinámica)?
Keith Randall el
77
-1. Preferiría una declaración autorizada con evidencia en lugar de lo que obviamente es solo una suposición.
Rob Kennedy el
Altamente improbable. Parece que no hay una buena razón para usar un montón (la estructura de datos) para administrar el montón (el conjunto de memoria libre).
Jason