为什么两个不同的概念都被称为“堆”?

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

Donald Knuth说(“计算机程序devise艺术”,第三版,第1卷,第435页):

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

他并没有说哪个作者,也没有提到任何具体的论文,但是确实说,在优先级队列中使用术语“堆”是传统意义上的单词。

他们有相同的名字,但他们真的不相似(甚至在概念上)。 一个内存堆被称为堆,就像你将一个洗衣篮称为一堆“衣服”一样。 这个名字是用来表示一个有点混乱的地方,可以随意分配和释放内存。 数据结构(如你参考的Wikipedia链接所指出的)是完全不同的。

名字相撞是不幸的,但并不是那么神秘。 是一个小的,常用的词,用来表示一堆,集合,组等等。数据结构这个词的用法是在预存date(我敢肯定)内存池的名字。 事实上,在我看来, 游泳池对于后者来说会是更好的select。 意味着一个垂直的结构(像一堆),它适合于数据结构,而不是内存池。 我们并不认为内存池堆是分层的,而数据结构背后的基本思想是将最大的元素保留在堆(和子堆)的顶部。

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

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

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

寻找可用内存分配的algorithm使用堆状数据结构。 以下摘自http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html

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

海事组织只是一个意外/巧合,这两个完全不相关的东西具有相同的名称。 它像graphics和graphics 。

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