Warum sind zwei verschiedene Konzepte genannt beide „Halde“?

Question

Warum sind die Common Language Runtime-Heap für dynamische Speicherzuweisung verwendet in C-Stil Sprachen und die Datenstruktur beide „der Halde“ genannt? Gibt es eine Beziehung?

Answer 1

Donald Knuth sagt (The Art of Computer Programming, Dritte Auflage, Band 1, S. 435...):

  

Mehrere Autoren etwa 1975 begannen, den Pool des verfügbaren Speichers zu nennen „Haufen.“

sagt er nicht, welche Autoren und nicht die Verweise auf bestimmte Papiere nicht geben, aber nicht sagen, dass die Verwendung der Begriffs „Halde“ in Bezug auf Prioritäts-Warteschlangen ist der traditionelle Sinn des Wortes.

Answer 2

Sie haben die gleichen Namen, aber sie sind wirklich nicht ähnlich (auch vom Konzept her). Ein Heap-Speicher ist ein Haufen in der gleichen Art und Weise genannt Sie zu einem Wäschekorb als „Kleiderhaufen“ bezeichnen würden. Dieser Name wird verwendet, um ein etwas chaotisch zugeht, um anzuzeigen, wo Speicher zugewiesen und nach Belieben ausgeplant werden können. Die Datenstruktur (wie Wikipedia Link verweisen weist darauf hin) ist ganz anders.

Answer 3

Der Name Kollision ist bedauerlich, aber nicht alles, was geheimnisvoll. Heap ist ein kleines, gemeinsames Wort verwendet, um eine Stapel, Sammlung, Gruppe bedeutet, usw. Die Verwendung des Wortes für die Datenstruktur vorgeDaten (ich bin mir ziemlich sicher) der Name des Pools Speicher. In der Tat, Pool wäre eine viel bessere Wahl für die letztere gewesen, meiner Meinung nach. Heap konnotiert eine vertikale Struktur (wie ein Stapel), die mit der Datenstruktur passt, aber nicht den Speicherpool. Wir glauben nicht, von einem Speicher-Pool-Heap als hierarchisch, während der Grundgedanke hinter der Datenstruktur ist das größte Element an der Spitze des Haufens zu halten (und Unterhalden).

Heap die Datenstruktur geht zurück auf die Mitte der 60er Jahre; Heap den Speicherpool, die frühen 70er Jahre. Der Begriff Heap (Speicherpool Bedeutung) wurde zumindest bereits 1971 von Wijngaarden in Diskussionen verwendet Algol.

Möglicherweise ist die früheste Verwendung von heap als Datenstruktur ist sieben Jahre zuvor gefunden in
Williams, J. W. J. 1964. "Algorithm 232 - Heapsort", Communications of the ACM 7 (6): 347-348

Answer 4

Eigentlich über die Art und Weise Speicher zu lesen (siehe Buddy Blocks ) zugeordnet erinnert mich ein Haufen in Datenstrukturen.

Answer 5

IMO ist es nur ein Unfall / Zufall, dass diese zwei völlig unabhängige Dinge denselben Namen haben. Es ist wie Graph und graph .

Answer 6

Heap-ähnliche Datenstruktur wird durch den Algorithmus der Suche nach verfügbarer Speicherzuweisung verwendet. Im Folgenden ist ein Auszug aus http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.

  

Wenn new aufgerufen wird, es beginnt mit der Suche nach einem freien Speicherblock, der die Größe Ihrer Anfrage paßt. Angenommen, dass ein solcher Speicherblock gefunden wird, wird es als reserviert markiert und einen Zeiger auf die Stelle zurückgegeben. Es gibt mehrere Algorithmen, dies zu erreichen, weil ein Kompromiss zwischen Scannen des gesamten Speichers gemacht werden muss für die Suche nach den kleinsten freien Block größer als die Größe des Objekts, oder die erste zurückkehrt, wo der Speicher passt benötigt. Um die Geschwindigkeit des Erhaltens einen Speicherblock, die freien und reservierten Speicherbereiche zu verbessern, sind in einer Datenstruktur ähnlich wie binäre Bäume ein Haufen genannt gehalten.

Answer 7

Die umgangssprachlichen Begriffen Stack-Speicher und Heap-Speicher nicht in dem C ++ Standard verwendet werden. Der Standard verwendet statische Lagerung, Gewindespeicher, automatische Speicherung und dynamische Speicher.

Mehr kann unter Lagerung Duraction Abschnitt der Norm gefunden werden .

Damit aus der Sprache und Standardbibliothek Sicht gibt es keine Verwirrung.

Answer 8

Q. Was ist ein Haufen? A. Ein Haufen ist eine Sammlung von Objekten auf der jeweils anderen Ort.

Antwort auf Ihre Frage: Beiden Speicherhaufen und binärer Heap verwenden das gleiche Konzept wie Sie wissen. Die Daten werden in der Form eines Haufens in dem Speicher in der gleichen Reihenfolge gespeichert, wie während binären Heap in dem Programm geschrieben ist eine Datenstruktur, die das gleiche Konzept der Speicherung von Daten in einer geordneten Art und Weise in Form eines Haufens (Data oben folgt von der anderen Seite). Lassen Sie mich wissen, was Sie in den Kommentaren denken.

Answer 9

Vielleicht ist der erste Speicher-Heap implementiert wurde von einem Heap-Struktur verwaltet?