数据结构：如果堆是树，为什么它们在内部用列表或数组实现？
Data Structures: If Heaps are trees, why are they implemented internally with Lists or arrays?
我正在给自己上一门数据结构和算法的进修课程（并学习新东西——我在大学主修信息系统而不是计算机科学，所以我没有接受过这些方面的正规教育), 我一直在研究堆。我有点困惑。
我的理解是 Heap 基本上是一个半排序树，其中每个子节点的值保证小于其父节点的值（本次讨论假设为 MinHeaps）。那么如果它是一棵树，为什么我看到的每个实现都在内部使用类似数组的结构而不是构建一组树节点？
我必须记住数组中 N 的子元素位于 2N + 1（左）和 2N + 2（右）*，这对我来说似乎很奇怪。为什么不直接构建一个具有 Left 和 Right 属性的节点，然后从那里开始呢？
*来源：This article
TL;DR：节省内存开销，从数据局部性获得更快的速度。
对于二叉树，您需要在每个节点中左 child 4 个字节，右 child 4 个字节（如果您使用的是 64 位系统，则为 8+8）。那只是您需要的裸指针。如果你存储一个 32 位的 int，那么开销很大。为将节点推向根所需的 parent 添加另一个指针，您正在查看 64 位系统上 4 字节整数的 24 字节开销。
对于堆，您无需担心任意树。您通常只关心头部（值的 min/max）而不关心内部结构。堆是一个几乎完整的二叉树（所有级别都被填充，除了最后一个从左到右填充）。在这个结构中，如果你只是把节点放在一个数组中，那么对于索引 x 处的节点，你总是会在 (x+1)/2 处找到 parent，在 [=12] 处找到左边的 child =] 和右边的 child 在 x*2+2。所以不需要存储任何那些胖指针。
除了节省 space 之外，您还可以获得速度提升，因为内存是连续的，因此更有可能将它们缓存在一起（不保证，更有可能）。
当然，如果它不是效率很重要的东西，你可以把它作为一个普通的树来实现。相反，如果你有一个几乎完整的树，并且你想充分利用你的系统，用一个数组来实现它（即使你不把它用作堆）。
首先，让我们稍微澄清一下词汇：
- 一个（面向最小值，但我不会每次都精确）优先级队列是一个抽象数据结构，它实现了操作
add和deleteMin，有时decreaseKey .实际上，您可以做一个简单的 array/list，在其中循环遍历结构以找到最小值，并且您会实现一个优先级队列（一个非常低效的队列，但仍然如此）。
A heap is a tree-based data structure that satisfies the heap property (Wikipedia)。堆 属性 是：父项的键值低于其子项。- 你描述的数据结构是很常见的binary heap，是堆的一种，但不是唯一的。 （也不是最有效的，但那是另一回事）。
第一次听说二叉堆的时候，我也觉得数组里有棵树很奇怪，而且还得做一些奇怪的乘法才能得到childs/parent。
很难在脑海中表现出来，但如果你仔细观察一下，它就非常有道理：
- 二叉堆几乎是平衡的，即数组中永远不会有空洞。 （这个简单的 属性 本身就很棒，因为数组中的空洞真的很痛苦）。
- 占用更少space：数组的内存效率比节点高得多。
- 按照设计，很容易将数组抽象为二叉树。您可以创建像
getRight(int node)、getLeft(int node) 和 getParent(int node) 这样的帮助程序，并且实现看起来会更熟悉。
然而，二叉堆的缓存效率不高，因为子节点离父节点很远，尽管它可能比基于节点的等效二叉堆的缓存效率更高。
现在如果你看优缺点，唯一的缺点是基于数组的二叉堆需要多一步才能在脑海中描绘出来，但它赢得了其他一切。
不知道原来的堆是不是设计成数组的，不知怎么的，有一天有人发现了这个实现，数组成了二叉堆的标准
然而，其他类型的堆是用节点实现的，所以这是一种特殊情况。
我正在给自己上一门数据结构和算法的进修课程（并学习新东西——我在大学主修信息系统而不是计算机科学，所以我没有接受过这些方面的正规教育), 我一直在研究堆。我有点困惑。
我的理解是 Heap 基本上是一个半排序树，其中每个子节点的值保证小于其父节点的值（本次讨论假设为 MinHeaps）。那么如果它是一棵树，为什么我看到的每个实现都在内部使用类似数组的结构而不是构建一组树节点？
我必须记住数组中 N 的子元素位于 2N + 1（左）和 2N + 2（右）*，这对我来说似乎很奇怪。为什么不直接构建一个具有 Left 和 Right 属性的节点，然后从那里开始呢？
*来源：This article
TL;DR：节省内存开销，从数据局部性获得更快的速度。
对于二叉树，您需要在每个节点中左 child 4 个字节，右 child 4 个字节（如果您使用的是 64 位系统，则为 8+8）。那只是您需要的裸指针。如果你存储一个 32 位的 int，那么开销很大。为将节点推向根所需的 parent 添加另一个指针，您正在查看 64 位系统上 4 字节整数的 24 字节开销。
对于堆，您无需担心任意树。您通常只关心头部（值的 min/max）而不关心内部结构。堆是一个几乎完整的二叉树（所有级别都被填充，除了最后一个从左到右填充）。在这个结构中，如果你只是把节点放在一个数组中，那么对于索引 x 处的节点，你总是会在 (x+1)/2 处找到 parent，在 [=12] 处找到左边的 child =] 和右边的 child 在 x*2+2。所以不需要存储任何那些胖指针。
除了节省 space 之外，您还可以获得速度提升，因为内存是连续的，因此更有可能将它们缓存在一起（不保证，更有可能）。
当然，如果它不是效率很重要的东西，你可以把它作为一个普通的树来实现。相反，如果你有一个几乎完整的树，并且你想充分利用你的系统，用一个数组来实现它（即使你不把它用作堆）。
首先，让我们稍微澄清一下词汇：
- 一个（面向最小值，但我不会每次都精确）优先级队列是一个抽象数据结构，它实现了操作
add和deleteMin，有时decreaseKey.实际上，您可以做一个简单的 array/list，在其中循环遍历结构以找到最小值，并且您会实现一个优先级队列（一个非常低效的队列，但仍然如此）。 A heap is a tree-based data structure that satisfies the heap property(Wikipedia)。堆 属性 是：父项的键值低于其子项。- 你描述的数据结构是很常见的binary heap，是堆的一种，但不是唯一的。 （也不是最有效的，但那是另一回事）。
第一次听说二叉堆的时候，我也觉得数组里有棵树很奇怪，而且还得做一些奇怪的乘法才能得到childs/parent。
很难在脑海中表现出来，但如果你仔细观察一下，它就非常有道理：
- 二叉堆几乎是平衡的，即数组中永远不会有空洞。 （这个简单的 属性 本身就很棒，因为数组中的空洞真的很痛苦）。
- 占用更少space：数组的内存效率比节点高得多。
- 按照设计，很容易将数组抽象为二叉树。您可以创建像
getRight(int node)、getLeft(int node)和getParent(int node)这样的帮助程序，并且实现看起来会更熟悉。
然而，二叉堆的缓存效率不高，因为子节点离父节点很远，尽管它可能比基于节点的等效二叉堆的缓存效率更高。
现在如果你看优缺点，唯一的缺点是基于数组的二叉堆需要多一步才能在脑海中描绘出来，但它赢得了其他一切。
不知道原来的堆是不是设计成数组的，不知怎么的，有一天有人发现了这个实现，数组成了二叉堆的标准
然而，其他类型的堆是用节点实现的，所以这是一种特殊情况。