堆到底是不是真的堆？

Question

可能重复：
为什么两个不同的概念都被称为“堆”？
“a”堆和“the”堆之间的关系是什么？

在.NET（以及据我所知的Java）中，动态分配对象的区域被称为托管堆。然而，大多数描述托管堆如何工作的文档描绘它为线性数据结构，例如链表或栈。

那么，托管堆实际上是一个堆，还是使用其他数据结构实现？如果它实际上没有使用堆数据结构，那么将这个词的含义重载似乎是一个重大的术语错误。

如果它实际上是一个堆数据结构，那么满足堆属性的值是什么：分配的内存区域的大小？

- newdayrising

---

+1 我已经想过这个问题了。 - CARLOS LOTH

请参见https://dev59.com/43I-5IYBdhLWcg3wu7Lv - John K

Answer 1

不，堆根本不是一个堆有序的二项树。现在还不清楚术语冲突是谁的错，但是堆的两种用法都可以追溯到几十年前（似乎是1970年代中期）。一些历史在这篇文章中讨论过。

- Martin v. Löwis

---

堆这个词可能已经超出了传统术语中数据结构的含义。我的意思是，如果不称之为“堆”，我们还能用什么来称呼它并教授它呢？ - John K

从《计算机程序设计艺术》中的历史参考可以得知，将一个问题分解成更小的子问题是一种有效的编程技巧。这种技巧被称为“分治法”，它在许多算法中都有应用。 - CARLOS LOTH

@John K：我不是英语母语者，所以“heap”对我来说并没有太多意义，除了计算机中的两种不同用法之外。如果我理解正确，传统用法等同于“堆积”。 - Martin v. Löwis

Answer 2

我确实没有历史知识来评论这个问题，但是我认为在.NET和Java中用于描述长期存在对象的内存分配机制的术语“堆”更多地是作为一个引人注目的、描述性的词语——就像一个大的无结构（从开发者的角度来看）的内存块，存放着东西。相比之下，“栈”的形象则唤起了一个更加有结构化的数据区域的形象（同样是从开发者的角度来看）：“东西”在栈上的存放位置比在堆上的存放位置更加相关。

这与实际的堆数据结构完全不同，后者使用“堆”一词来指代所谓的堆属性（来自维基百科）:

如果B是A的子节点，则key(A) ≥ key(B)。

所以它们实际上是没有关联的。一个只是一个描述性的术语，而另一个则有一个更加正式的定义。

- Dan Tao

Answer 3

在这个意义上，“堆”指的是：一个用于存储重要资源的特殊内存区域。在这种情况下，它与“堆数据结构”无关。

- CARLOS LOTH

Answer 4

我不确定我的答案是否正确，但据我所知，在像C#或Java这样的语言中，由垃圾回收器管理内存区域并非是线性的。GC会释放可以释放的内存，并在内存不足时压缩内存进行某种碎片整理。它移动程序使用的内存块以在“末尾”腾出一些空间。

你为什么需要这个答案？你想进行一些低级内存管理吗？

- Mat