Ari*_*oth 4 algorithm data-structures array-algorithms
我正在给自己上数据结构和算法的进修课程（并学习新东西——我在大学主修信息系统而不是计算机科学，所以我没有接受这些方面的正规教育），而且我“一直在研究堆。我有点困惑。
我的理解是堆基本上是一棵半排序树，其中每个子节点的值都保证小于其父节点的值（假设本讨论为 MinHeaps）。那么，如果它是一棵树，为什么我见过的每个实现都在内部使用了类似数组的结构，而不是构建一组树节点？
我必须记住数组中 N 的子节点位于 2N + 1（左）和 2N + 2（右）* 处，这对我来说似乎很奇怪。为什么不直接构建一个具有 Left 和 Right 属性的节点并从那里开始呢？
*来源：本文
Sor*_*rin 10
TL;DR：节省内存开销，从数据本地获得更高的速度。
对于二叉树，您需要在每个节点中为左子节点分配 4 个字节，为右子节点分配 4 个字节（如果在 64 位系统上，则为 8+8）。这只是您需要的裸指针。如果您存储 32 位 int，那将是很多开销。为将节点推向根节点所需的父节点添加另一个指针，并且您正在查看 64 位系统上 4 字节整数的 24 字节开销。
对于堆，您无需担心任意树。您通常只担心头部（值的最小值/最大值），而不关心内部结构。堆是一个几乎完整的二叉树（除了最后一层从左到右填充外，所有级别都被填充）。在这个结构中，如果你只是将节点放在一个数组中，那么对于 index 处的节点，x你总是在(x+1)/2左子节点atx*2+1和右子节点处找到父节点at x*2+2。所以不需要存储任何这些胖指针。
除了节省的空间外，您还可以获得速度提升，因为内存是连续的，因此更有可能将其缓存在一起（不能保证，只是更有可能）。
当然，如果效率不重要，您可以将其实现为常规树。相反，如果你有一个几乎完整的树，并且你想最大限度地利用你的系统用一个数组来实现它（即使你不将它用作堆）。