Why are two different concepts both called “heap”?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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