为什么C语言风格的语言会使用运行时堆来进行动态内存分配，而数据结构也被称为“堆”？它们之间有关联吗？
为什么两个不同的概念都被称为“堆”？
230
- Andrey Fedorov
4
6今天在学习数据结构时，我想知道这个问题的答案。 - MitMaro
1重复的问题？https://dev59.com/AHRA5IYBdhLWcg3w_DHF - timB33
3请打开一本英文字典并查找"Run"这个词条，统计其中适用于计算机的词义数量。在40多个词义中，有多少个适用于计算机？ :) - jmucchiello
这里有一个相关的帖子，涉及动态内存分配所使用的运行时堆。 - RBT
9个回答
115
唐纳德·克努斯（Donald Knuth）在《计算机程序设计艺术》第三版第一卷第435页中说：
大约从1975年开始，一些作者将可用内存池称为“堆”。
他没有说出是哪些作者，并且没有提供任何具体论文的参考文献，但是他确实说，在与优先队列相关的术语中，“堆”这个词的传统含义是指可用内存池。
- James McNellis
7
16“池”比“堆”更合适作为名称。 - user181548
7有趣。有人应该问他是否记得是哪些作者。 - Prof. Falken
36维基百科声称早期的Lisp使用堆（一种数据结构）来实现其内存存储。但它没有说明具体方法。它的参考文献是“Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms. MIT Press / McGraw-Hill.”，但我没有此书。 - Steve Jessop
5我没有相关的参考资料，但我的猜测是最初用于组织对开放内存块的引用的数据结构是最小堆。这似乎至少是一种快速查找能够存储您要存储的数据的最小内存块的不错方式。更新：我的说法听起来就像“伙伴块”http://en.wikipedia.org/wiki/Dynamic_memory_allocation#Buddy%5Fblocks - Will
6在堆排序的章节开头，查看Cormen、Leiserson、Rivest和Stein的《算法导论》第3版（2009年），它仅表示“‘heap’一词最初是在堆排序的上下文中被创造出来的，但是现在它已经指代了‘垃圾收集存储器’，例如Java和Lisp等编程语言所提供的。我们的堆数据结构不是垃圾收集存储器，而且每当我们在本书中提到堆时，我们都指的是数据结构而不是垃圾收集的方面。” 《算法导论》第2版同样使用了几乎相同的措辞（没有表明Lisp使用了堆）。 - dr jimbob
显示剩余2条评论
83
它们的名字相同，但它们并不相似（即使在概念上）。内存堆被称为“heap”，就像您将洗衣筐称为“一堆衣服”一样。这个名字用于指示一个有点凌乱的位置，可以任意地分配和释放内存。数据结构（正如您所引用的维基百科链接所指出的那样）是相当不同的。
- Andrew Hare
5
9我认为这正是他提出问题的要点：它们是不同的。那么为什么它们被称为相同的东西-是否存在某种潜在的关系。 - Sean Owen
13我理解这个回答的意思是“没有基本关系”，因此它回答了问题。 - Laurence Gonsalves
安德鲁正在回答那个问题。它们之间没有关系，只是巧合。内存堆更符合常规用法，因为内存分配就像“一堆衣服”。然而，数据结构需要更大的想象力。这变成了一个更有趣的“为什么”。名称来自于节点按其键排序，而父节点键始终大于或等于其子节点的事实。 - Alexandre Bell
8它们绝对无关。然而称它为“堆”存在一个问题，因为“堆”的对应物——“栈”——也是一个实际的栈结构。 - dan
2我知道为什么堆数据结构被称为堆：因为它满足堆属性。但是为什么堆属性叫做这个名字呢？对我来说没有意义，一个像“顶重”的名字会更好。 - Thomas Eding
44
名称冲突很不幸，但并不神秘。"Heap"是一个常用的小词，用来表示堆、集合、组等。数据结构中使用这个单词的时间比内存池的名称要早得多（我非常确定）。实际上，在我看来，"pool"应该是后者更好的选择。"Heap"暗示了一种垂直的结构（像一堆东西），这符合数据结构，但不符合内存池。我们不认为内存池堆是分层的，而数据结构背后的基本思想是将最大的元素保持在堆的顶部（和子堆）。
堆这个数据结构可以追溯到60年代中期；堆这个内存池则是在70年代初出现的。至少在1971年，"heap"（指内存池）这个术语就已经在Wijngaarden关于Algol的讨论中使用过了。
可能最早将"heap"用作数据结构的例子可以在7年前的Williams, J. W. J. 1964. "Algorithm 232 - Heapsort", Communications of the ACM 7(6): 347-348中找到。
- I. J. Kennedy
6
3是的，但“堆”也暗示着混乱和记忆堆通常是无序的。数据结构“堆”非常有序。因此，基于常见的“堆”定义，双向的不匹配现象同样存在。 - jmucchiello
1它总是被介绍为stack的相反，这应该足以解释其名称。 - reinierpost
1这不是巧合 - 自由列表可以通过二项堆实现为优先队列。 - Heath Hunnicutt
TL;DR; Broken english :) - Cristian E.
如果计算机科学界能够为这些命名惯例设立一个标准机构，那将是非常好的。我们绝对应该将操作系统堆重命名为“池”。 - iono
8
实际上，阅读有关内存分配方式的文章（请参见Buddy Blocks）让我想起了数据结构中的堆。
- Traveling Tech Guy
1
我对Peter Zhang的答案的评论在这里也是相关的。二进制伙伴系统可以表示为二叉树，并且当每个节点的“键”是它下面的总内存时，它看起来也像一个有效的最大堆（但这些值是隐式的且永远不会改变）。据我所知，分配和释放算法都没有在这个二叉树上使用堆操作。 - Eric Dubé
7
堆数据结构被用于寻找可用内存分配的算法。以下内容摘自http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html。
当调用
new时，它会开始查找一个适合你请求大小的空闲内存块。假设找到了这样一个内存块，它将被标记为已保留，并返回指向该位置的指针。由于需要在扫描整个内存中查找最小的大于对象大小的空闲块之间做出折衷，或者返回第一个满足所需内存的块，因此有几种算法可以实现这一点。为了提高获取内存块的速度，所以维护了一个类似于二叉树的数据结构，称为堆来存储空闲和保留的内存区域。
- Peng Zhang
2
2我对这个非常怀疑，特别是"...自由和保留的内存区域是在一个类似于二叉树的数据结构中维护的，称为堆。"听起来作者是在猜测有一个联系，基于名字 "堆"，并且可能是错误的。有人能确认/驳斥吗？ - Don Hatch
1经过对Linux中使用的二进制伙伴系统进行了一些轻微的研究，由于它如何分割数据，它可以被表示为二叉树。如果您从总内存的角度观察节点，则此二叉树看起来像有效的最大堆，但是节点不会像最大堆那样直接插入到此二叉树中-节点将直接插入到空闲内存>=请求大小的最小叶子中。[1]（https://www.kernel.org/doc/gorman/html/understand/understand009.html）
[2]（https://www.youtube.com/watch?v=1pCC6pPAtio）
[3]（https://www.youtube.com/watch?v=t0Cq6tVNRBA） - Eric Dubé
-2
Q. 什么是堆(heap)？ A. 堆(heap)是一组对象按照顺序堆叠在一起的集合。
回答你的问题： 无论是内存堆还是二叉堆，都使用了相同的概念。 数据以堆(heap)的形式按照程序中编写的顺序存储在内存中，而二叉堆是一种数据结构，遵循相同的概念，以堆(heap)的形式有序地存储数据(数据放在其他数据之上)。 请在评论区告诉我你的想法。
- Mayank Tolani
1
2内存堆和二叉堆使用相同的概念，正如您所知道的那样。但是内存堆和堆数据结构没有任何共同之处。 - Kaiyaha
-5
也许最早实现的内存堆是由一个堆结构来管理的？
- Adam Maras
3
8这个假设似乎并不明显——堆（数据结构）如何对维护堆（动态内存区域）有用呢？ - Keith Randall
8我更喜欢有证据的权威声明，而不是显然只是猜测的东西。 - Rob Kennedy
极不可能。似乎没有充分的理由使用堆（数据结构）来管理堆（空闲内存池）。 - jason
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接