为什么 C 风格语言中用于动态内存分配的运行时堆和数据结构都称为“堆”?有什么关系吗?
9 回答
Donald Knuth 说(计算机编程的艺术,第三版,第 1 卷,第 435 页):
几位作者在 1975 年左右开始将可用内存池称为“堆”。
他没有说是哪些作者,也没有给出任何具体论文的参考文献,但确实说“堆”这个词与优先级队列有关是这个词的传统含义。
它们具有相同的名称,但实际上并不相似(甚至在概念上)。内存堆被称为堆,就像您将洗衣篮称为“衣服堆”一样。该名称用于表示可以随意分配和释放内存的有些杂乱的地方。数据结构(正如您引用的维基百科链接所指出的)完全不同。
名字冲突是不幸的,但并不是那么神秘。堆是一个小而常见的词,用于表示堆、集合、组等。该词用于数据结构早于(我很确定)内存池的名称。事实上,在我看来,对于后者来说, pool会是一个更好的选择。堆意味着一个垂直的结构(像一堆),它适合数据结构,但不适合内存池。我们不认为内存池堆是分层的,而数据结构背后的基本思想是将最大的元素保持在堆(和子堆)的顶部。
堆数据结构可以追溯到 60 年代中期;堆内存池,70年代初。至少早在 1971 年,Wijngaarden在讨论 Algol 时就使用了术语堆(意思是内存池)。
堆作为数据结构的最早使用可能是七年前在
Williams,JWJ 1964 中发现的。“算法 232 - Heapsort”,ACM 通信7(6):347-348
实际上,阅读内存分配方式(参见Buddy Blocks)让我想起了数据结构中的堆。
查找可用内存分配的算法使用类堆数据结构。以下内容摘自http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html。
当
new
被调用时,它开始寻找适合您请求大小的空闲内存块。假设找到这样的内存块,将其标记为保留并返回指向该位置的指针。有几种算法可以实现这一点,因为必须在扫描整个内存以找到大于对象大小的最小空闲块或返回所需内存适合的第一个空闲块之间做出折衷。为了提高获取内存块的速度,内存的空闲和保留区域被维护在一个类似于二叉树的数据结构中,称为堆。
问:什么是堆?A. 堆是相互重叠的对象集合。
回答您的问题:内存堆和二进制堆都使用您所知道的相同概念。数据以与程序中写入相同的顺序以堆的形式存储在内存中,而二进制堆是一种数据结构,遵循以堆的形式以有序方式存储数据的相同概念(顶部的数据另一个)。在评论部分让我知道你的想法。
也许实现的第一个内存堆是由堆结构管理的?