Talk:Dynamic memory allocation

From Wikipedia, the free encyclopedia

[edit] Two meanings of heaps

Can someone please expand the section "Heap-based memory allocation"? How exactly is the Heap data structure utilized in it? thx!

It isn't! Just a coincidence in naming. Good point. Usually the heap is based on one of the discussed allocation algorithms such as free lists or the buddy system. Deco 01:53, 29 December 2005 (UTC)

Do we know of the history of why it got to be called 'heap' instead of an infinite number of other things and who was the person or company who used the term heap first?

I'm guessing now, but the terms could be related: A simple implementation of the (memory allocation) heap is to represent the set of free blocks using a (max-)heap data structure, where the keys are block sizes. Allocation is greedy: Take the largest free block (top of the heap), allocate a sufficient portion of it, and perform decrease-key on the top of the heap. To deallocate memory, just add it to the heap. With this method, allocation and deallocation is simple and fast, but it probably gives huge problems with memory fragmentation. --Erik 16:18, 10 February 2006 (UTC)

That is an interesting point. But yes, consistently allocating from the largest block seems doomed to cause rapid fragmentation. However, although I don't have a source on this, historically I believe the terms both originated from the English concept of a heap of stuff, rather than having any relation to one another. Deco 18:40, 10 February 2006 (UTC)