arrays - 使用链表的二进制堆的复杂性

Question

我正在尝试使用数组和链表比较实现二进制堆。我认为数组在各方面都更好，因为所有操作都可以比使用链表的操作更快或相等。它还需要更少的内存。

但是，为什么使用链表比二进制堆中的数组更好，有什么理由吗？

Answer 1

二进制堆很少被表示为显式树。它们比数组版本使用更多的内存，引用的局部性很差，并且（正如您在之前的问题中指出的那样）更难实现。

将二叉堆作为树来研究的主要原因是建立对数据结构的直觉。仅给定数组表示，很难推断二叉堆的属性和正确性，但是通过将它们连接回二叉树表示，设计和证明二叉堆算法的正确性变得容易得多。

希望这可以帮助！