为什么两个不同的概念都被称为"堆"？

Question

为什么两个不同的概念都被称为"堆"？

And*_*rov 144 c++ heap terminology heap-memory

为什么运行时堆用于C风格语言中的动态内存分配,数据结构都称为"堆"？有一些关系吗？

Answer 1

Jam*_*lis 67

唐纳德克努特说(计算机编程艺术,第三版,第1卷,第435页):

几位作者在1975年开始将可用内存池称为"堆".

他没有说明哪些作者并没有提及任何具体论文,但确实说与优先级队列相关的术语"堆"的使用是传统意义上的.

维基百科声称这是因为在早期阶段,Lisp使用堆(数据结构)来实现其内存存储.它没有说明如何.它的参考文献是"Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest(1990):算法导论.麻省理工学院出版社/ McGraw-Hill.",我没有. (24认同)
池比堆更好. (10认同)
有趣.有人应该问他是否还记得哪些作者. (7认同)
@SteveJessop - 检查Cormen,Leiserson,Rivest,Stein - 第3版(2009年),在Heapsort章节的开头,它只说"术语"堆"最初是在heapsort的背景下创造的,但它后来指的是"垃圾收集存储,"如Java和Lisp提供的编程语言.我们的堆数据结构不是垃圾收集存储,每当我们在本书中引用堆时,我们将指的是数据结构而不是垃圾收集的一个方面.CLRS - 第2版也有几乎完全相同的措辞(没有迹象表明Lisp使用了Heap). (3认同)
我没有参考,但我的猜测是,最初用于组织对打开的内存块的引用的数据结构是一个最小堆.看起来它至少是一种很好的方式,可以快速找到最小的内存块,允许你存储你试图存储的数据更新:我所说的听起来就像伙伴块http://en.wikipedia.org /维基/ Dynamic_memory_allocation#巴迪%5Fblocks (2认同)
唐纳德是对的，这是一个不幸的命名冲突。特别是对于非母语人士，例如，您真的，他们第一次遇到“堆”这个词是在他们的数据结构课程中。我称它为堆，一直认为它是类堆结构，直到今天我决定了解类堆结构如何用于内存分配。我有点生气：/ (2认同)

Answer 2

And*_*are 54

它们具有相同的名称但它们实际上并不相似(甚至在概念上).内存堆称为堆,就像您将洗衣篮称为"衣服堆"一样.此名称用于指示一个有点混乱的地方,可以随意分配和释放内存.数据结构(如您引用的Wikipedia链接所指出的)是完全不同的.

我解释这个答案的方式是"不,没有潜在的关系",所以它回答了这个问题. (8认同)
是的,我认为这是他提出问题的重点:他们是不同的.那么为什么他们被称为同一件事 - 是否有一些潜在的关系. (7认同)
他们肯定是无关的.然而,将其称为"堆"的问题是"堆"对应 - "堆栈" - 也是实际堆栈. (4认同)
我知道为什么堆数据结构被称为堆：因为它满足堆属性。但是为什么堆属性这么叫呢？这对我来说毫无意义，因为像“头重脚轻”这样的名字会好得多。 (2认同)

Answer 3

I. *_*edy 30

名字碰撞是不幸的,但不是那么神秘.堆是一个小的,常用的词,用于表示堆,集合,组等.使用单词作为数据结构的前置日期(我很确定)内存池的名称.事实上,在我看来,游泳池对后者来说是一个更好的选择.堆意味着垂直结构(如堆),它适合数据结构,但不适合内存池.我们不认为内存池堆是分层的,而数据结构背后的基本思想是将最大元素保持在堆的顶部(和子堆).

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

可能最早使用堆作为数据结构是七年前在
威廉姆斯,JWJ 1964 年发现的."算法232 - Heapsort",ACM通讯 7(6):347-348

是的，但是堆也意味着无序，而内存堆通常是无序的。数据结构堆是非常有序的。因此，基于堆的通用定义，同样存在相反的不匹配。 (2认同)
@jmucchiello:一堆日志(见[图片](http://www.shutterstock.com/pic-71326984/stock-photo-wood-exploitation-heap-of-logs-in-forest.html))很好有序和树状的.根据我的本科教科书之一,这是数据结构名称的起源. (2认同)

Answer 4

Tra*_*Guy 6

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

Answer 5

Pen*_*ang 6

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

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

我对此非常怀疑，特别是“......内存的空闲和保留区域被维护在类似于二叉树的数据结构中，称为堆”。在我看来，作者根据“堆”这个名字猜测两者之间存在联系，并且可能是错误的。有人能证实/反驳吗？ (2认同)

Answer 6

MAK*_*MAK 5

国际海事组织这两个完全不相关的事情具有相同的名称只是偶然/巧合.它像图形和图形.

@Amit:对于连续图形,意味着无限数量的顶点.这没关系,但这也使得顶点之间的边缘概念毫无意义.在函数f(x)= x*2的图中,是否存在(0,0)和(1,2)之间的边？如果是,那么(0,0)和(0.5,1)怎么样？(0,0)和(0.25,0.5)？没有办法在顶点之间设置边缘的概念,因此这不是一个图形. (2认同)

归档时间：	15 年，11 月前
查看次数：	20750 次
最近记录：	6 年，4 月前