开发者

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

This question already has answers here: 开发者_如何转开发 Closed 12 years ago.

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?


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.)


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


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜