What's the connection between the heap used in dynamic memory allocation and the data structure?

Question

Possible Duplicate:
Why are two different concepts both called “heap”?

I've googled around, but cannot find the answer for this question; what's the connection between the heap used in dynamic memory allocation and the data structure? Is memory organized on the heap in a way which is similar the the heap data structure? If so, this seems very strange, since fetching memory should be random access AFAIK (i.e, O(1)), but finding an item from a heap is not done in constant time.

So, is this just an overloaded meaning of heap, so to speak, or is there some kind of connection?

Answer 1

Heap is a synonym for what the standard calls the free-store. In contrast to stacks, which is used for function calls, and function-local object storage, heaps grow in the opposite direction (top to bottom) on many implementations (as opposed to stacks -- which grow from bottom to top). Of course, none of these are required by the standard.

The heap data structure, on the other hand is completely different -- it is a specialized tree structure with certain properties.

It is possible some implementations use the heap data structure for free-store management, whence the name may have been derived. (See buddy memory allocation.)

Answer 2

No, the program heap is different from the heap data structure. In other words, no relation. This question discusses the program heap in detail.

Answer 3

There is no relation, but I admit the name can be confusing. The heap in memory is an array that the OS allocates to programs. A heap is implemented by programs for fast lookup.