Is the heap actually a heap? [duplicate]

Question

Possible Duplicates:
Why are two different concepts both called “heap”?
What's the relationship between “a” heap and “the” heap?

In .NET (and Java as far as I know), the area where objects are dynamically allocated is referred to as the managed heap. However, most documentation that describes how the managed heap works depicts it as a linear data structure, such as a linked list or stack.

So, is the managed heap actually a heap, or is it implemented with some other data structure? If it actually does not use a heap data structure, is seems like a significant failure of terminology to overload the meaning of this word.

If it is in fact a heap data structure, what is the value that satisfies the heap property: the size of the allocated memory region?

Answer 1

No, the heap is not a heap-ordered binomial tree at all. It's not clear (to me) whose fault the terminology clash is, but both uses of heap date back decades now (mid-1970, it appears). Some of the history is discussed in this article.

Answer 2

I certainly don't have the historical knowledge to comment on this with any authority, but I believe the term "heap" as employed to describe the memory allocation mechanism for longer-lived objects in .NET and Java is more intended as an evocative, descriptive word—like, this big unstructured (from the dev's viewpoint) mass of memory where stuff lives. The "stack" in contrast evokes the image of a much more structured region of data (again, from the dev's viewpoint): "where" things live on the stack feels a lot more relevant than "where" they live on the heap.

This is clearly very different from the actual heap data structure, which uses the word "heap" to refer to the so-called heap property (from Wikipedia):

if B is a child node of A, then key(A) ≥ key(B).

So yeah, they're actually unrelated. One is just a descriptive term whereas the other has a much more formal definition.