我正在给自己上一门数据结构和算法的进修课程(并学习新东西——我在大学里主修信息系统，而不是计算机科学，所以我没有接受过这些方面的正式教育)，我一直在做大量的工作。我有点困惑。
我的理解是，堆基本上是一个半排序树，其中每个子节点的值都保证小于其父节点的值(在本讨论中假设为MinHeaps)。那么，如果它是一棵树，为什么我看到的每个实现都在内部使用类似数组的结构，而不是构建一组树节点呢？
我觉得很奇怪，我必须记住一个数组中N的孩子坐在2N+1(左)和2N+2(右)*。为什么不构建一个具有Left和Right属性的节点，然后从那里开始呢？
*来源：本文
TL；DR：节省内存开销，从数据本地化中获得更高的速度。
对于二进制树，您需要在每个节点中为左子节点提供4个字节，为右子节点提供四个字节(如果您使用64位系统，则为8+8)。这只是你所需要的最基本的指示。如果您存储一个32位的int，那将是一个很大的开销。为将节点推向根所需的父节点添加另一个指针，在64位系统上，4字节整数的开销为24字节。
对于堆，您不需要担心任意的树。您通常只关心头部(值的最小值/最大值)，而不关心内部结构。堆是一个几乎完整的二叉树(除了从左到右填充的最后一个外，所有级别都被填充)。在这个结构中，如果你只把节点放在一个数组中，那么对于索引为x的节点，你总是在(x+1)/2找到父节点，在x*2+1找到左子节点，在x*2+2找到右子节点。所以不需要存储任何这些胖指针。
除了节省空间外，您还可以提高速度，因为内存是连续的，因此更有可能将其缓存在一起(不能保证，只是更有可能)。
当然，如果它不是效率很重要的东西，你可以把它实现为一个普通的树。相反，如果你有一个几乎完整的树，并且你想最大限度地利用你的系统，用一个数组来实现它(即使你不把它用作堆)。
首先，让我们对词汇表做一点澄清：
- 优先级队列是一种抽象的数据结构，它实现了操作
add和deleteMin，有时还实现了decreaseKey。实际上，您可以制作一个简单的数组/列表，在其中循环遍历结构以找到最小值，并且您将实现一个优先级队列(虽然效率很低，但仍然如此) A heap is a tree-based data structure that satisfies the heap property(维基百科)。堆属性是：父级的键比其子级的键低- 您所描述的数据结构是非常常见的二进制堆，它是一种堆，但不是唯一的堆。(不是最有效的，但那是另一回事)
当我第一次听说二进制堆时，我还认为在数组中有一棵树是非常奇怪的，你必须进行一些奇怪的乘法运算才能到达子/父。
在你的脑海中表达它更困难，但如果你仔细看一看，它是完全有意义的：
- 二进制堆几乎是平衡的，也就是说，数组中永远不会有洞。(这个简单的属性本身就非常棒，因为数组中的洞真的很痛苦)
- 它占用的空间更少：数组比节点的内存效率高得多
- 在设计时，很容易将数组抽象为二叉树。您可以创建像
getRight(int node)、getLeft(int node)和getParent(int node)这样的帮助程序，实现看起来会更加熟悉
然而，二进制堆的缓存效率并不高，因为子堆离父堆很远，尽管它可能比基于节点的等效二进制堆更高效。
现在，如果你看看利弊，唯一的缺点是基于数组的二进制堆需要再多走一步才能在脑海中描绘出来，但它赢得了其他一切。
我不知道最初的堆是否被设计成数组，但不知何故，有一天有人发现了这个实现，数组已经成为二进制堆的标准。
然而，其他类型的堆是用节点实现的，所以这是一种特殊情况。