Pourquoi deux concepts différents sont-ils appelés «heap»?

Pourquoi le tas d’exécution utilisé pour l’allocation dynamic de mémoire dans les langages de style C et la structure de données sont-ils tous deux appelés “le tas”? Y a-t-il une relation?

Donald Knuth dit (The Art of Computer Programming, troisième édition, vol. 1, p. 435):

Plusieurs auteurs ont commencé vers 1975 à appeler le pool de mémoire disponible un “tas”.

Il ne dit pas quels auteurs et ne donne aucune référence à 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.

Ils ont le même nom mais ils ne sont pas vraiment similaires (même conceptuellement). Un tas de mémoire s’appelle un tas de la même manière que vous qualifieriez un panier à linge de “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 libérée à volonté. La structure de données (comme l’indique le lien Wikipedia que vous avez mentionné) est très différente.

La collision de noms est regrettable, mais pas si mystérieuse. Heap est un petit mot commun utilisé pour désigner une stack, une collection, un groupe, etc. L’utilisation du mot pour la structure de données précède (je suis sûr) le nom du pool de mémoire. En fait, le pool aurait été un choix bien meilleur pour ce dernier, à mon avis. Heap connote une structure verticale (comme une stack), qui correspond à la structure des données, mais pas au pool de mémoire. Nous ne considérons pas un tas de 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 sumt du tas (et des sous-segments).

Entasser la structure des données remonte au milieu des années 60; entasser le pool de mémoire, au début des années 70. Le terme heap (signifiant pool de mémoire) a été utilisé au moins dès 1971 par Wijngaarden dans les discussions d’Algol.

Peut-être la première utilisation de tas comme une structure de données se trouve sept ans plus tôt dans
Williams, JWJ 1964. “Algorithme 232 – Heapsort”, Communications de l’ACM 7 (6): 347-348

En fait, la lecture de la manière dont la mémoire est allouée (voir Blocs de contacts ) me rappelle un tas de structures de données.

IMO, c’est simplement un accident / une coïncidence si ces deux choses totalement indépendantes ont le même nom. C’est comme graphique et graphique .

La structure de données en tas est utilisée 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 commence à rechercher un bloc de mémoire libre correspondant à la taille de votre requête. En supposant qu’un tel bloc de mémoire soit trouvé, il est marqué comme réservé et un pointeur vers cet emplacement est renvoyé. Il existe plusieurs algorithmes pour y parvenir, car il faut faire un compromis entre parsingr toute la mémoire pour trouver le plus petit bloc libre plus grand que la taille de votre object ou retourner le premier où la mémoire est nécessaire. Afin d’améliorer la vitesse d’obtention d’un bloc de mémoire, les zones de mémoire libres et réservées sont conservées dans une structure de données similaire aux arborescences binarys appelée segment de mémoire.

Peut-être que le premier segment de mémoire implémenté a été géré par une structure de segment de mémoire?

Les termes familiers de la mémoire de stack et de la mémoire de stack ne sont pas utilisés dans la norme C ++. La norme utilise le stockage statique, le stockage de threads, le stockage automatique et le stockage dynamic.

Vous trouverez plus d’ informations dans la section Storage Duraction de la norme.

Par conséquent, du sharepoint vue du langage et de la bibliothèque standard, il n’y a pas de confusion.