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, JWJ 1964. "Algorithm 232 - Heapsort", Communications of the ACM 7(6): 347-348
上一篇: 堆，堆栈和永久代
下一篇: 为什么两个不同的概念都被称为“堆”？