Why are two different concepts both called "heap"?

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?

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.

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.

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. We don't think of a memory-pool heap as hierarchical, whereas the fundamental idea behind the data structure is keeping the largest element at the top of the heap (and sub-heaps).

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 years earlier in
Williams, J. W. J. 1964. "Algorithm 232 - Heapsort", Communications of the ACM 7(6): 347-348

Actually, reading about the way memory is allocated (see Buddy Blocks) reminds me of a heap in data structures.

Heap-like data structure is used by algorithm of finding available memory allocation. The following is excerpted from http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.

>When new is invoked, it starts looking for a free memory block that fits the size for your request. Supposing that such a block of memory is found, it is marked as reserved and a pointer to that location is returned. There are several algorithms to accomplish this because a compromise has to be made between scanning the whole memory for finding the smallest free block bigger than the size of your object, or returning the first one where the memory needed fits. In order to improve the speed of getting a block of memory, the free and reserved areas of memory are maintained in a data structure similar to binary trees called a heap.

IMO it is merely an accident/coincidence that these two entirely unrelated things have the same name. Its like graph and graph.

The colloquial terms stack memory and heap memory are not used in the C++ standard. The standard uses static storage, thread storage, automatic storage, and dynamic storage.

More can be found at Storage Duraction section of the standard.

Hence, from the language and standard library point of view, there is no confusion.

Q. What is a heap? A. A heap is a collection of objects place on top of each other.

Answer to your question: Both memory heap and binary heap uses the same concept as you know. Data is stored in the form of a heap in the memory in the same order as written in the program whereas binary heap is a data structure that follows the same concept of storing data in an ordered way in the form of a heap(Data on top of the other). Let me know what you think in the comments section.

Perhaps the first memory heap implemented was managed by a heap structure?