Warum werden zwei verschiedene Konzepte als "Haufen" bezeichnet?

170

Warum werden der Laufzeitheap für die dynamische Speicherzuweisung in Sprachen im C-Stil und die Datenstruktur als "Heap" bezeichnet? Gibt es eine Beziehung?

c++ heap terminology heap-memory Andrey Fedorov
quelle
4
Ich habe mich heute beim Studium der Datenstrukturen gefragt.
MitMaro
1
doppelte Frage? http://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap
timB33
3
Gehen Sie zu einem englischen Wörterbuch und zählen Sie die Anzahl der Einträge unter "Ausführen". Wie viele der über 40 Einträge gelten für Computer? :)
jmucchiello
2
Mögliches Duplikat von Wie ist die Beziehung zwischen "einem" Heap und "dem" Heap?
RCIX
Ein verwandter Beitrag hier zum Laufzeit-Heap, der für die dynamische Speicherzuweisung verwendet wird.
RBT

Antworten:

77

Donald Knuth sagt (The Art of Computer Programming, 3. Aufl., Bd. 1, S. 435):

Mehrere Autoren begannen ungefähr 1975, den Pool des verfügbaren Speichers als "Haufen" zu bezeichnen.

Er sagt nicht, welche Autoren und gibt keine Verweise auf bestimmte Artikel, aber er sagt, dass die Verwendung des Begriffs "Haufen" in Bezug auf Prioritätswarteschlangen der traditionelle Sinn des Wortes ist.

James McNellis
quelle
11
Pool wäre ein besserer Name als Haufen.
7
Interessant. Jemand sollte ihn fragen, ob er sich an welche Autoren erinnert.
Prof. Falken
27
Wikipedia behauptet, es liege daran, dass Lisp in einem frühen Stadium einen Heap (Datenstruktur) verwendet habe, um seinen Speicher zu implementieren. Es sagt nicht wie. Seine Referenz ist "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Einführung in Algorithmen. MIT Press / McGraw-Hill.", Was ich nicht habe.
Steve Jessop
2
Ich habe keine Referenz dafür, aber ich würde vermuten, dass die Datenstruktur, die zum Organisieren von Referenzen auf offene Speicherblöcke verwendet wurde, anfangs ein Min-Heap war. Es scheint zumindest eine gute Möglichkeit zu sein, schnell den kleinsten Speicherblock zu finden, mit dem Sie die Daten speichern können, die Sie speichern wollten. Update: Was ich gesagt habe, klingt genau wie Buddy-Blöcke. En.wikipedia.org/wiki/Dynamic_memory_allocation # Buddy% 5Fblocks
Will
4
@SteveJessop - Überprüfung von Cormen, Leiserson, Rivest, Stein - 3. Auflage (2009) zu Beginn des Heapsort-Kapitels heißt es nur: "Der Begriff" Heap "wurde ursprünglich im Zusammenhang mit Heapsort geprägt, bezieht sich aber seitdem auf" Speicherbereinigung ", wie die Programmiersprachen Java und Lisp. Unsere Heap-Datenstruktur besteht nicht aus Speicherbereinigungen, und wenn wir in diesem Buch auf Heaps verweisen, meinen wir eher eine Datenstruktur als einen Aspekt der Speicherbereinigung. ' CLRS - 2nd Edition hat auch fast genau die gleiche Formulierung (kein Hinweis darauf, dass Lisp einen Heap verwendet hat).
Dr. Jimbob
64

Sie haben den gleichen Namen, sind sich aber nicht wirklich ähnlich (auch nicht konzeptionell). Ein Speicherhaufen wird als Haufen bezeichnet, so wie Sie einen Wäschekorb als "Kleiderhaufen" bezeichnen würden. Dieser Name wird verwendet, um einen etwas unordentlichen Ort anzuzeigen, an dem Speicher nach Belieben zugewiesen und freigegeben werden kann. Die Datenstruktur (wie der Wikipedia-Link zeigt, auf den Sie verweisen) ist ganz anders.

Andrew Hare
quelle
8
Ja, ich denke, das ist eher der Punkt, auf den er seine Frage stützt: Sie sind unterschiedlich. Warum werden sie also dasselbe genannt - gibt es eine zugrunde liegende Beziehung?
Sean Owen
9
Die Art und Weise, wie ich diese Antwort interpretierte, ist "Nein, es gibt keine zugrunde liegende Beziehung", also beantwortet sie die Frage.
Laurence Gonsalves
Andrew antwortet darauf. Es gibt keine Beziehung. Nur ein Zufall. Der Speicherhaufen entspricht eher der allgemeinen Verwendung, da der Speicher wie ein "Kleiderhaufen" zugewiesen wird. Die Datenstruktur erforderte jedoch ein größeres Maß an Vorstellungskraft. Und dies wird ein viel interessanteres "Warum". Der Name kommt von der Tatsache, dass Knoten nach ihrem Schlüssel angeordnet sind und ein übergeordneter Knotenschlüssel immer> = als sein untergeordneter Knoten ist.
Alexandre Bell
6
Sie sind definitiv nicht verwandt. Das Problem bei der Bezeichnung "der Heap" ist jedoch, dass "das" Gegenstück des Heaps - "der Stapel" - auch ein tatsächlicher Stapel ist.
Dan
1
Ich weiß, warum die Heap-Datenstruktur als Heap bezeichnet wird: weil sie die Heap-Eigenschaft erfüllt. Aber warum heißt die Heap-Eigenschaft so? Es macht für mich keinen Sinn, da ein Name wie "kopflastig" viel besser wäre.
Thomas Eding
31

Die Namenskollision ist unglücklich, aber nicht so mysteriös. Heap ist ein kleines, gebräuchliches Wort, das einen Stapel, eine Sammlung, eine Gruppe usw. bedeutet. Die Verwendung des Wortes für die Datenstruktur datiert (ich bin mir ziemlich sicher) vor dem Namen des Speicherpools. In der Tat wäre Pool meiner Meinung nach eine viel bessere Wahl für Letzteres gewesen. Heap bezeichnet eine vertikale Struktur (wie ein Stapel), die zur Datenstruktur passt, nicht jedoch zum Speicherpool. Wir betrachten einen Speicherpool-Heap nicht als hierarchisch, während die Grundidee hinter der Datenstruktur darin besteht, das größte Element oben auf dem Heap (und den Sub-Heaps) zu halten.

Die Datenstruktur stammt aus der Mitte der 60er Jahre. Haufen den Speicherpool, die frühen 70er Jahre. Der Begriff Heap (Speicherpool) wurde mindestens 1971 von Wijngaarden in Diskussionen über Algol verwendet.

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

IJ Kennedy
quelle
1
Ja, aber ein Heap impliziert auch eine Störung, und Speicherhaufen sind im Allgemeinen ungeordnet. Der Datenstruktur-Heap ist sehr gut geordnet. Es gibt also wieder eine gleiche Nichtübereinstimmung, die auf der Grundlage der gemeinsamen Definition von Heap in die andere Richtung geht.
jmucchiello
Es wird immer als das Gegenteil von Stapel eingeführt, was ausreichen sollte, um den Namen IMO zu erklären.
Reinierpost
1
Es ist kein Zufall - die freie Liste kann als Prioritätswarteschlange über einen Binomialheap implementiert werden.
Heath Hunnicutt
2
@jmucchiello: Ein Haufen Holz (siehe Bild ) ist gut geordnet und baumähnlich. Dies ist der Ursprung des Namens der Datenstruktur gemäß einem meiner Lehrbücher für Studenten.
Gioele
6

Das Lesen über die Art und Weise, wie Speicher zugewiesen wird (siehe Buddy-Blöcke ), erinnert mich an einen Haufen in Datenstrukturen.

Travelling Tech Guy
quelle
Mein Kommentar zu Peter Zhangs Antwort ist auch hier relevant. Das binäre Buddy-System kann als binärer Baum dargestellt werden, und es sieht auch so aus, als ob ein gültiger maximaler Heap dies tut, wenn der "Schlüssel" jedes Knotens der Gesamtspeicher darunter ist (diese Werte sind jedoch implizit und ändern sich nie). Soweit ich das beurteilen kann, verwenden weder der Zuordnungs- noch der Freigabealgorithmus Heap-Operationen für diesen Binärbaum.
Eric Dubé
5

IMO ist es nur ein Zufall / Zufall, dass diese beiden völlig unabhängigen Dinge den gleichen Namen haben. Es ist wie Grafik und Grafik .

MAK
quelle
Die beiden Graphen können jedoch irgendwie zusammenhängen. Stellen Sie sich den Graphen einer Funktion wie folgt vor: Die Tupeldomäne (Bereich) ist ein Scheitelpunkt und eine Kante verbindet zwei solcher Scheitelpunkte
2
@Amit: Für kontinuierliche Diagramme würde dies eine unendliche Anzahl von Eckpunkten bedeuten. Das ist in Ordnung, aber das macht auch das Konzept der Kanten zwischen den Eckpunkten bedeutungslos. Gibt es im Diagramm der Funktion f (x) = x * 2 eine Kante zwischen (0,0) und (1,2)? Wenn ja, wie wäre es mit (0,0) und (0,5,1)? (0,0) und (0,25,0,5)? Es gibt keine Möglichkeit, das Konzept einer Kante zwischen Scheitelpunkten zu haben, daher ist dies nicht wirklich ein Diagramm.
MAK
5

Die Heap-ähnliche Datenstruktur wird vom Algorithmus zum Ermitteln der verfügbaren Speicherzuordnung verwendet. Das Folgende ist ein Auszug aus http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html .

Wenn newes aufgerufen wird, sucht es nach einem freien Speicherblock, der der Größe Ihrer Anfrage entspricht. Angenommen, ein solcher Speicherblock wird gefunden, wird er als reserviert markiert und ein Zeiger auf diesen Speicherort wird zurückgegeben. Es gibt verschiedene Algorithmen, um dies zu erreichen, da ein Kompromiss zwischen dem Scannen des gesamten Speichers, um den kleinsten freien Block zu finden, der größer als die Größe Ihres Objekts ist, oder dem Zurückgeben des ersten Blocks, in den der benötigte Speicher passt. Um die Geschwindigkeit beim Abrufen eines Speicherblocks zu verbessern, werden die freien und reservierten Speicherbereiche in einer Datenstruktur verwaltet, die Binärbäumen ähnelt, die als Heap bezeichnet werden.

Peng Zhang
quelle
1
Ich bin äußerst skeptisch, insbesondere "... die freien und reservierten Speicherbereiche werden in einer Datenstruktur verwaltet, die Binärbäumen ähnelt, die als Heap bezeichnet werden." Es klingt für mich so, als würde der Autor vermuten, dass es eine Verbindung gibt, die auf dem Namen "Heap" basiert, und sich wahrscheinlich irrt. Kann jemand bestätigen / widerlegen?
Don Hatch
1
Nach einigen leichten Recherchen zum Binary Buddy-System (unter Linux verwendet) kann es aufgrund der Partitionierung von Daten durch einen Binärbaum dargestellt werden. Dieser Binärbaum sieht aus wie ein gültiger maximaler Heap, wenn Sie die Knoten in Bezug auf den Gesamtspeicher beobachten, aber Knoten werden nicht wie in einem maximalen Heap in diesen Binärbaum eingefügt - Knoten werden direkt in das kleinste Blatt des freien Speichers eingefügt> = die gewünschte Größe. 1 2 3
Eric Dubé
1

Die umgangssprachlichen Begriffe Stapelspeicher und Heapspeicher werden im C ++ - Standard nicht verwendet. Der Standard verwendet statischen Speicher, Thread-Speicher, automatischen Speicher und dynamischen Speicher.

Weitere Informationen finden Sie im Abschnitt Speicherdauer des Standards.

Aus Sicht der Sprache und der Standardbibliothek gibt es daher keine Verwirrung.

R Sahu
quelle
1

F. Was ist ein Haufen? A. Ein Haufen ist eine Sammlung von Objekten, die übereinander liegen.

Antwort auf Ihre Frage: Sowohl der Speicherheap als auch der Binärheap verwenden dasselbe Konzept wie Sie wissen. Daten werden in Form eines Heaps im Speicher in derselben Reihenfolge wie im Programm gespeichert gespeichert, während binärer Heap eine Datenstruktur ist, die dem gleichen Konzept folgt, Daten in geordneter Weise in Form eines Heaps zu speichern (Daten oben) des anderen). Lassen Sie mich wissen, was Sie in den Kommentaren denken.

Mayank Tolani
quelle
-2

Vielleicht wurde der erste implementierte Speicherheap von einer Heap-Struktur verwaltet?

Adam Maras
quelle
8
Diese Hypothese scheint überhaupt nicht offensichtlich zu sein - wie ist ein Heap (die Datenstruktur) überhaupt nützlich, um einen Heap (den dynamischen Speicherbereich) aufrechtzuerhalten?
Keith Randall
7
-1. Ich würde eine maßgebliche Aussage mit Beweisen vorziehen, anstatt offensichtlich nur eine Vermutung.
Rob Kennedy
Sehr unwahrscheinlich. Es scheint keinen guten Grund zu geben, einen Heap (die Datenstruktur) zu verwenden, um den Heap (den Pool des freien Speichers) zu verwalten.
Jason