¿Por qué son dos conceptos diferentes ambos llamados “montón”?

Question

¿Por qué el montón de tiempo de ejecución utilizado para la asignación dinámica de memoria en lenguajes de tipo C y la estructura de datos tanto llama "el montón"? ¿Hay alguna relación?

Answer 1

Donald Knuth dice (The Art of Computer Programming, tercera edición, Vol 1, p 435...):

  

Varios autores comenzaron el año 1975 para llamar la piscina de memoria disponible un "montón".

No dice que los autores y no haga mención de cualquier documento específicos, pero sí dice que el uso del término "montón" en relación con colas de prioridad es el sentido tradicional de la palabra.

Answer 2

Tienen el mismo nombre pero que en realidad no son similares (incluso conceptualmente). Un montón de memoria se llama un montón de la misma forma que lo haría referencia a un cesto de la ropa como un "montón de ropa". Este nombre se utiliza para indicar un lugar algo desordenado donde la memoria se puede asignar y desasignar a voluntad. La estructura de datos (como el enlace de Wikipedia se hace referencia señala) es bastante diferente.

Answer 3

El nombre de la colisión es lamentable, pero no todo lo que misterioso. Montón es una palabra pequeña, común usado para referirse a una pila, colección, grupo, etc. El uso de la palabra para la estructura de datos es anterior a (estoy bastante seguro) el nombre de la piscina de la memoria. De hecho, piscina habría sido una opción mucho mejor para el último, en mi opinión. Montón connota una estructura vertical (como una pila), que encaja con la estructura de datos, pero no el bloque de memoria. No creemos que un montón de memoria de grupo como jerárquica, mientras que la idea fundamental detrás de la estructura de datos es mantener el elemento más grande en la parte superior de la pila (y sub-montones).

Heap la estructura de datos se remonta a mediados de los años 60; amontonar el bloque de memoria, a principios de los años 70. Se utiliza el término montón (que significa bloque de memoria) al menos tan temprano como 1971 por Wijngaarden en las discusiones de Algol.

Posiblemente el uso más antiguo de heap como una estructura de datos se encontró siete años antes en
Williams, J. W. J. 1964. "Algoritmo 232 - heapsort", Comunicaciones de la ACM 7 (6): 347-348

Answer 4

En realidad, la lectura de la memoria de forma se asigna (ver de Buddy Bloques ) me recuerda de un montón en estructuras de datos.

Answer 5

OMI no es más que un accidente / coincidencia que estas dos cosas sin relación alguna con el mismo nombre. Es como gráfico y gráfico .

Answer 6

estructura de datos del montón como es utilizado por el algoritmo de búsqueda de asignación de memoria disponible. El siguiente es un extracto de http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.

  

Cuando se invoca new, comienza la búsqueda de un bloque de memoria libre que se ajuste al tamaño de su solicitud. Suponiendo que un bloque de memoria como se encuentra, se marca como reservada y se devuelve un puntero a esa ubicación. Existen varios algoritmos para lograr esto debido a un compromiso tiene que ser hecha entre el escaneo de 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 en el que la memoria necesita ajustes. Con el fin de mejorar la velocidad de conseguir un bloque de memoria, las zonas libres y reservada de la memoria se mantienen en una estructura de datos similar a los árboles binarios llamados un montón.

Answer 7

Los términos coloquiales pila de memoria y la memoria de pila no se utilizan en el estándar de C ++. El estándar utiliza almacenamiento estático, almacenamiento de hilo, almacenamiento automático, y de almacenamiento dinámico.

Más se puede encontrar en de almacenamiento Duraction sección de la norma .

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

Answer 8

Q. ¿Qué es un montón? A. Un montón es una colección de objetos coloque en la parte superior de la otra.

respuesta a su pregunta: Tanto montón de memoria y pila binaria utiliza el mismo concepto que sabes. Los datos se almacenan en forma de un montón en la memoria en el mismo orden como está escrito en el programa mientras que pila binaria es una estructura de datos que sigue el mismo concepto de almacenamiento de datos de una forma ordenada en la forma de un montón (Datos en la parte superior del otro). Déjame saber lo que piensa en la sección de comentarios.

Answer 9

Tal vez el primer montón de memoria implementado fue gestionado por una estructura de pila?