Pourquoi sont deux concepts différents deux appelés « tas »?

Question

Pourquoi le tas d'exécution utilisé pour l'allocation dynamique de la mémoire dans les langues de style C et la structure de données tous les deux appelés « le tas »? Y at-il une relation?

Answer 1

Donald Knuth dit (L'art de la programmation informatique, troisième édition, vol 1, p 435...):

  

Plusieurs auteurs ont commencé vers 1975 pour appeler la piscine de mémoire disponible un « tas ».

Il ne dit pas que les auteurs et ne donne pas de références à des documents spécifiques, mais ne dit que l'utilisation du terme « tas » par rapport aux files d'attente prioritaires est le sens traditionnel du mot.

Answer 2

Ils ont le même nom, mais ils ne sont pas vraiment similaires (même sur le plan conceptuel). Un tas de mémoire est appelé un tas de la même façon que vous référer à un panier à linge comme un « tas de vêtements ». Ce nom est utilisé pour indiquer un endroit un peu en désordre où la mémoire peut être allouée et désallouée à volonté. La structure de données (comme le lien de Wikipedia, les points de référence out) est tout à fait différent.

Answer 3

La collision de nom est regrettable, mais pas du tout mystérieuse. Heap est un petit mot couramment utilisé pour désigner une pile, collection, groupe, etc. L'utilisation du mot pour la structure de données date d'avant (je suis sûr) le nom de la piscine de la mémoire. En fait, Piscine aurait été un bien meilleur choix pour ce dernier, à mon avis. Heap connote une structure verticale (comme une pile), ce qui correspond à la structure de données, mais pas la piscine de mémoire. Nous ne pensons pas d'un tas-pool mémoire hiérarchique, alors que l'idée fondamentale derrière la structure de données maintient le plus grand élément en haut du tas (et sous-tas).

Heap la structure de données remonte au milieu des années 60; tas du pool de mémoire, au début des années 70. Le tas terme (ce qui signifie pool de mémoire) a été utilisé au moins aussi tôt que 1971 par Wijngaarden dans les discussions Algol.

Peut-être la première utilisation de tas en tant que structure de données se trouve sept ans plus tôt dans
Williams, J. W. J. 1964. "algorithme 232 - Heapsort", Communications de l'ACM 7 (6): 347-348

Answer 4

En fait, la lecture de la mémoire est allouée façon (voir blocs de Buddy ) me rappelle d'un segment de mémoire dans les structures de données.

Answer 5

l'OMI, il est simplement un accident / un hasard si ces deux choses tout à fait sans rapport avec le même nom. Son comme et graphique .

Answer 6

structure de données du tas-like est utilisé par l'algorithme de recherche de l'allocation de mémoire disponible. Ce qui suit est extrait de http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.

  

Lorsque new est appelé, il se met à la recherche d'un bloc de mémoire libre qui correspond à la taille de votre demande. En supposant qu'un tel bloc de mémoire se trouve, il est marqué comme réservé et un pointeur vers cet endroit est retourné. Il y a plusieurs algorithmes pour le faire parce qu'un compromis doit être fait entre le balayage de la mémoire entier pour trouver le plus grand bloc libre plus petit que la taille de votre objet ou retourner le premier où la mémoire nécessaire crises. Afin d'améliorer la vitesse d'obtenir un bloc de mémoire, les zones libres et réservées de mémoire sont maintenues dans une structure de données similaire aux arbres binaires appelés un tas.

Answer 7

Les termes familiers pile mémoire et la mémoire du segment de mémoire ne sont pas utilisés dans la norme C ++. La norme utilise la mémoire statique, le stockage de fil, le stockage automatique et de stockage dynamique.

En savoir plus peut être trouvé à section Stockage Duraction de la norme .

Par conséquent, de la langue et du point de vue de la bibliothèque standard, il n'y a pas de confusion.

Answer 8

Q. Qu'est-ce qu'un tas? A. Un tas est une collection d'objets placer sur le dessus de l'autre.

Réponse à votre question: Les deux tas de mémoire et tas binaire utilise le même concept que vous savez. Les données sont stockées sous la forme d'un tas dans la mémoire dans le même ordre que celui écrit dans le programme alors tas binaire est une structure de données qui suit le même concept de stockage de données d'une manière ordonnée sous la forme d'un segment de mémoire (données sur le dessus de l'autre). Faites-moi savoir ce que vous pensez dans la section des commentaires.

Answer 9

Peut-être le premier segment de mémoire mis en œuvre a été gérée par une structure de tas?