Why are the runtime heap used for dynamic memory allocation in C-style languages and the data structure both called "the heap"? Is there some relation?
+1
A:
Perhaps the first memory heap implemented was managed by a heap structure?
Adam Maras
2009-11-09 04:15:45
That hypothesis doesn't seem at all obvious - how is a heap (the data structure) at all useful for maintaining a heap (the dynamic memory region)?
Keith Randall
2009-11-09 04:42:50
-1. I would prefer an authoritative statement with evidence instead of what's obviously just a guess.
Rob Kennedy
2009-11-09 07:19:46
Highly unlikely. There seems to be no good reason to use a heap (the data structure) to manage the heap (the pool of free memory).
Jason
2009-11-09 20:01:19
+12
A:
They have the same name but they really aren't similar (even conceptually). A memory heap is called a heap in the same way you would refer to a laundry basket as a "heap of clothes". This name is used to indicate a somewhat messy place where memory can be allocated and deallocated at will. The data structure (as the Wikipedia link you reference points out) is quite different.
Andrew Hare
2009-11-09 04:17:23
Yes, I think that's rather the point on which he's basing his question: they are different. So why are they called the same thing -- is there some underlying relation.
Sean Owen
2009-11-09 04:25:17
The way I interpreted this answer is "no, there is no underlying relation", so it answers the question.
Laurence Gonsalves
2009-11-09 04:52:55
Andrew is answering that. There's no relation. Just a coincidence. The memory heap is more true to the common usage since memory is allocated as if a "heap of clothes". The data structure however demanded a larger stretch of imagination. And this becomes a rather much more interesting "why". The name comes from the fact nodes are arranged by their key and a parent node key is always >= than its child node.
Krugar
2009-11-09 04:57:23
+2
A:
Actually, reading about the way memory is allocated (see Buddy Blocks) reminds me of a heap in data structures.
Traveling Tech Guy
2009-11-09 04:20:51
+11
A:
Donald Knuth says (The Art of Computer Programming, Third Ed., Vol. 1, p. 435):
Several authors began about 1975 to call the pool of available memory a "heap."
He doesn't say which authors and doesn't give references to any specific papers, but does say that the use of the term "heap" in relation to priority queues is the traditional sense of the word.
James McNellis
2009-11-09 04:47:09
+1
A:
We asked this question of some of our Computer Science professors and they did not have the answer as well. Kind of mysterious actually...
Bryan Harrington
2009-11-09 04:51:56
Welcome to Stack Overflow. Although you are encouraged to answer questions as well as ask them, perhaps this wasn't the best choice for your first answer since it doesn't actually *answer* the question. It would have been more appropriate as a comment (although you don't get to comment on arbitrary posts until you get a high enough "reputation").
Rob Kennedy
2009-11-09 07:27:25
+1
A:
IMO it is merely an accident/coincidence that these two entirely unrelated things have the same name. Its like graph and graph.
MAK
2009-11-09 05:19:41
The two graphs can though somehow be related. Imagine the graph of a function as follows: The tuple domain,range) is a vertex and a edge connects two such vertices
Amit
2009-11-09 05:46:23
@Amit: For continuous graphs that would mean an infinite number of vertices. This is ok, but that also makes the concept of edges between the vertices meaningless. In the graph of the function f(x)=x*2, is there an edge between (0,0) and (1,2)? If yes, how about (0,0) and (0.5,1)? (0,0) and (0.25,0.5)? There is no way of having the concept of an edge between vertices, so this is not really a graph.
MAK
2009-11-09 19:28:12
+7
A:
The name collision is unfortunate, but not all that mysterious. Heap is a small, common word used to mean a pile, collection, group, etc. The use of the word for the data structure pre-dates (I'm pretty sure) the name of the pool of memory. In fact, pool would have been a much better choice for the latter, in my opinion. Heap connotes a vertical structure (like a pile), which fits with the data structure, but not the memory pool.
Heap the data structure dates back to the mid-60s; heap the memory pool, the early-70s. The term heap (meaning memory pool) was used at least as early as 1971 by Wijngaarden in discussions of Algol.
Possibly the earliest use of heap as a data structure is found seven year earlier in
Williams, J. W. J. 1964. "Algorithm 232 - Heapsort", Communications of the ACM 7(6): 347-348
I. J. Kennedy
2009-11-09 05:24:59
Yes, but a heap also implies disorder and memory heaps are generally disordered. The data structure heap is extremely well ordered. So again there's an equal mismatch going the other way based on the common definition of heap.
jmucchiello
2009-11-10 01:24:42
+1
A:
duplicate question? http://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap
queBurro
2009-11-09 09:54:13