C++ 为什么两个不同的概念都称为“堆”？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1699057/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Why are two different concepts both called "heap"?
提问by Andrey Fedorov
Why are the runtime heap used for dynamic memory allocation in C-style languages and the data structureboth called "the heap"? Is there some relation?
为什么运行时堆在 C 风格语言中用于动态内存分配，而数据结构都称为“堆”？有什么关系吗？
采纳答案by James McNellis
Donald Knuth says (The Art of Computer Programming, Third Ed., Vol. 1, p. 435):
Donald Knuth 说（计算机编程的艺术，第三版，第 1 卷，第 435 页）：
Several authors began about 1975 to call the pool of available memory a "heap."
一些作者在 1975 年左右开始将可用内存池称为“堆”。
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.
他没有说明是哪位作者，也没有给出任何具体论文的参考，但确实说，与优先级队列相关的术语“堆”的使用是该词的传统含义。
回答by Andrew Hare
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.
它们具有相同的名称，但实际上并不相似（甚至在概念上）。内存堆被称为堆，就像将洗衣篮称为“衣服堆”一样。此名称用于指示可以随意分配和释放内存的有点混乱的地方。数据结构（正如您引用的维基百科链接所指出的）完全不同。
回答by I. J. Kennedy
The name collision is unfortunate, but not all that mysterious. Heapis 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, poolwould have been a much better choice for the latter, in my opinion. Heapconnotes 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).
名称冲突是不幸的，但并不是那么神秘。堆是一个小的、常用的词，用于表示堆、集合、组等。数据结构这个词的使用早于（我很确定）内存池的名称。事实上，在我看来，pool对于后者来说是一个更好的选择。堆意味着垂直结构（就像一堆），它适合数据结构，但不适合内存池。我们不认为内存池堆是分层的，而数据结构背后的基本思想是将最大的元素保留在堆（和子堆）的顶部。
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 Wijngaardenin discussions of Algol.
堆的数据结构可以追溯到 60 年代中期；堆内存池，70 年代初。至少早在 1971 年，Wijngaarden在讨论 Algol 时就使用了术语堆（意思是内存池）。
Possibly the earliest use of heapas a data structure is found seven years earlier in
Williams, J. W. J. 1964. "Algorithm 232 - Heapsort", Communications of the ACM7(6): 347-348
最早使用堆作为数据结构的可能是 7 年前在
Williams, JWJ 1964 中发现的。“算法 232 - 堆排序”，ACM 通信7(6)：347-348
回答by Traveling Tech Guy
Actually, reading about the way memory is allocated (see Buddy Blocks) reminds me of a heap in data structures.
实际上，阅读内存分配方式（参见Buddy Blocks）让我想起了数据结构中的堆。
回答by Peng Zhang
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.
查找可用内存分配的算法使用类似堆的数据结构。以下摘自http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html。
When
newis 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.
当
new被调用时，它开始寻找适合您请求大小的空闲内存块。假设找到了这样的内存块，则将其标记为保留并返回指向该位置的指针。有几种算法可以实现这一点，因为必须在扫描整个内存以找到大于对象大小的最小空闲块或返回第一个适合内存需要的块之间进行折衷。为了提高获取内存块的速度，内存的空闲和保留区域都维护在一种类似于二叉树的数据结构中，称为堆。
回答by MAK
回答by R Sahu
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.
C++ 标准中不使用口语术语堆栈内存和堆内存。该标准使用静态存储、线程存储、自动存储和动态存储。
More can be found at Storage Duraction sectionof the standard.
更多信息可以在标准的存储持续时间部分找到。
Hence, from the language and standard library point of view, there is no confusion.
因此，从语言和标准库的角度来看，没有混淆。
回答by Mayank Tolani
Q. What is a heap? A. A heap is a collection of objects place on top of each other.
问：什么是堆？A. 堆是放置在彼此之上的对象的集合。
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.
回答您的问题：内存堆和二进制堆都使用您所知道的相同概念。数据以堆的形式存储在内存中的顺序与程序中写入的顺序相同，而二进制堆是一种数据结构，其遵循相同的概念，即以堆的形式（数据在顶部）以有序的方式存储数据另一个）。在评论部分告诉我你的想法。
回答by Adam Maras
Perhaps the first memory heap implemented was managed by a heap structure?
也许第一个实现的内存堆是由堆结构管理的？
