204

为什么 C 风格语言中用于动态内存分配的运行时堆和数据结构都称为“堆”?有什么关系吗?

4

9 回答 9

100

Donald Knuth 说(计算机编程的艺术,第三版,第 1 卷,第 435 页):

几位作者在 1975 年左右开始将可用内存池称为“堆”。

他没有说是哪些作者,也没有给出任何具体论文的参考文献,但确实说“堆”这个词与优先级队列有关是这个词的传统含义。

于 2009-11-09T04:47:09.770 回答
74

它们具有相同的名称,但实际上并不相似(甚至在概念上)。内存堆被称为堆,就像您将洗衣篮称为“衣服堆”一样。该名称用于表示可以随意分配和释放内存的有些杂乱的地方。数据结构(正如您引用的维基百科链接所指出的)完全不同。

于 2009-11-09T04:17:23.987 回答
39

名字冲突是不幸的,但并不是那么神秘。是一个小而常见的词,用于表示堆、集合、组等。该词用于数据结构早于(我很确定)内存池的名称。事实上,在我看来,对于后者来说, pool会是一个更好的选择。意味着一个垂直的结构(像一堆),它适合数据结构,但不适合内存池。我们不认为内存池堆是分层的,而数据结构背后的基本思想是将最大的元素保持在堆(和子堆)的顶部。

堆数据结构可以追溯到 60 年代中期;堆内存池,70年代初。至少早在 1971 年,Wijngaarden在讨论 Algol 时就使用了术语堆(意思是内存池)。

作为数据结构的最早使用可能是七年前在
Williams,JWJ 1964 中发现的。“算法 232 - Heapsort”,ACM 通信7(6):347-348

于 2009-11-09T05:24:59.793 回答
6

实际上,阅读内存分配方式(参见Buddy Blocks)让我想起了数据结构中的堆。

于 2009-11-09T04:20:51.337 回答
6

查找可用内存分配的算法使用类堆数据结构。以下内容摘自http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html

new被调用时,它开始寻找适合您请求大小的空闲内存块。假设找到这样的内存块,将其标记为保留并返回指向该位置的指针。有几种算法可以实现这一点,因为必须在扫描整个内存以找到大于对象大小的最小空闲块或返回所需内存适合的第一个空闲块之间做出折衷。为了提高获取内存块的速度,内存的空闲和保留区域被维护在一个类似于二叉树的数据结构中,称为堆。

于 2014-11-02T19:10:00.573 回答
5

IMO 这两个完全不相关的事物具有相同的名称只是一个意外/巧合。它就像graphgraph

于 2009-11-09T05:19:41.937 回答
2

C++ 标准中不使用俗称的堆栈内存和堆内存。该标准使用静态存储、线程存储、自动存储和动态存储。

更多信息可以在标准的存储持续时间部分找到。

因此,从语言和标准库的角度来看,没有混淆。

于 2018-03-16T16:20:20.227 回答
0

问:什么是堆?A. 堆是相互重叠的对象集合。

回答您的问题:内存堆和二进制堆都使用您所知道的相同概念。数据以与程序中写入相同的顺序以堆的形式存储在内存中,而二进制堆是一种数据结构,遵循以堆的形式以有序方式存储数据的相同概念(顶部的数据另一个)。在评论部分让我知道你的想法。

于 2019-06-25T12:20:11.290 回答
-5

也许实现的第一个内存堆是由堆结构管理的?

于 2009-11-09T04:15:45.840 回答