Pourquoi le tas d'exécution est-il utilisé pour l'allocation dynamique de la mémoire dans les langages de type C et les langages de type B ? la structure des données tous deux appelés "le tas" ? Y a-t-il un rapport ?
Donald Knuth dit (The Art of Computer Programming, Third Ed., Vol. 1, p. 435) :
Plusieurs auteurs ont commencé vers 1975 à appeler le pool de mémoire disponible un "tas".
Il ne précise pas quels sont les auteurs et ne donne pas de références à des articles spécifiques, mais dit que l'utilisation du terme "tas" en relation avec les files d'attente prioritaires est le sens traditionnel du mot.
Wikipedia affirme que c'est parce qu'à un stade précoce, Lisp a utilisé un tas (structure de données) pour mettre en œuvre son magasin de mémoire. Elle ne dit pas comment. Sa référence est "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990) : Introduction aux algorithmes. MIT Press / McGraw-Hill", que je n'ai pas.
Ils portent le même nom mais ne sont pas vraiment similaires (même conceptuellement). Un tas de mémoire est appelé "tas" de la même manière que vous appelleriez un panier à linge un "tas de vêtements". Ce nom est utilisé pour indiquer un endroit quelque peu désordonné où la mémoire peut être allouée et désallouée à volonté. La structure des données (comme l'indique le lien Wikipedia auquel vous faites référence) est très différente.
Oui, je pense que c'est plutôt le point sur lequel il base sa question : ils sont différents. Alors pourquoi les appelle-t-on de la même façon ? Y a-t-il une relation sous-jacente ?
La façon dont j'ai interprété cette réponse est "non, il n'y a pas de relation sous-jacente", donc elle répond à la question.
Andrew est en train de répondre à cette question. Il n'y a aucun rapport. Juste une coïncidence. Le tas de mémoire est plus fidèle à l'usage courant puisque la mémoire est allouée comme un "tas de vêtements". La structure de données, par contre, demande une plus grande imagination. Et cela devient un "pourquoi" beaucoup plus intéressant. Le nom vient du fait que les nœuds sont classés par leur clé et que la clé d'un nœud parent est toujours >= celle de son nœud enfant.
La collision des noms est malheureuse, mais pas si mystérieuse que ça. Amas est un petit mot courant utilisé pour désigner un tas, une collection, un groupe, etc. L'utilisation de ce mot pour désigner la structure de données est antérieure (j'en suis presque sûr) au nom du pool de mémoire. En effet, piscine aurait été un bien meilleur choix pour ce dernier, à mon avis. Amas évoque une structure verticale (comme une pile), ce qui correspond à la structure des données, mais pas au pool de mémoire. Nous ne considérons pas le tas d'un pool de mémoire comme hiérarchique, alors que l'idée fondamentale derrière la structure de données est de garder le plus grand élément au sommet du tas (et des sous tas).
La structure de données "heap" date du milieu des années 60 ; le "heap", le pool de mémoire, du début des années 70. Le terme "heap" (qui signifie "pool de mémoire") a été utilisé au moins dès 1971 par les auteurs suivants Wijngaarden dans les discussions sur Algol.
Il est possible que la plus ancienne utilisation de amas en tant que structure de données est trouvé sept ans plus tôt dans
Williams, J. W. J. 1964. "Algorithme 232 - Heapsort", Communications de l'ACM 7(6) : 347-348
Oui, mais un tas implique aussi le désordre et les tas de mémoire sont généralement désordonnés. Le tas de la structure de données est extrêmement bien ordonné. Donc, une fois encore, il y a un décalage égal dans l'autre sens sur la base de la définition commune du tas.
Il est toujours présenté comme l'opposé de pile ce qui devrait suffire à expliquer le nom IMO.
Ce n'est pas une coïncidence : la liste libre peut être implémentée comme une file d'attente prioritaire via un tas binomial.
En fait, en lisant sur la façon dont la mémoire est allouée (voir Blocs de copains ) me fait penser à un tas dans les structures de données.
Mon commentaire sur la réponse de Peter Zhang est également pertinent ici. Le système de binôme binaire peut être représenté comme un arbre binaire, et il ressemble également à un tas max valide lorsque la "clé" de chaque nœud est la valeur total la mémoire en dessous (mais ces valeurs sont implicites et ne changent jamais). Ni l'algorithme d'allocation ni celui de libération n'utilisent d'opérations de tas sur cet arbre binaire, pour autant que je sache.
Les deux graphiques peuvent cependant être reliés d'une manière ou d'une autre. Imaginez le graphe d'une fonction comme suit : Le tuple domain,range) est un sommet et une arête relie deux de ces sommets.
@Amit : Pour les graphes continus, cela signifierait un nombre infini de sommets. C'est ok, mais cela rend aussi le concept d'arêtes entre les sommets sans signification. Dans le graphe de la fonction f(x)=x*2, y a-t-il une arête entre (0,0) et (1,2) ? Si oui, qu'en est-il de (0,0) et (0,5,1) ? (0,0) et (0,25,0,5) ? Il n'y a aucun moyen d'avoir le concept d'une arête entre les sommets, donc ce n'est pas vraiment un graphe.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
4 votes
Je me suis posé cette question aujourd'hui en étudiant les structures de données.
1 votes
Question en double ? http://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap
3 votes
Consultez un dictionnaire anglais et comptez le nombre d'entrées sous "Run". Sur plus de 40 entrées, combien s'appliquent aux ordinateurs ? :)
2 votes
Duplicata possible de Quelle est la relation entre "un" tas et "le" tas ?
0 votes
Un billet connexe ici par rapport au tas d'exécution utilisé pour l'allocation dynamique de la mémoire.