ome*_*ega 11 heap tree big-o binary-tree
在创建二进制最大堆时,为什么最好将它实现为基于数组,而不是基于树(基于树,每个节点也有一个指向它的父节点)？在运行时分析,内存使用,性能......
对于二进制最大堆,运行时间为:
对于树实现
谁能详细解释一下？
树使用更多的时间和内存.复杂性是相同的,但常数因素是不同的.
与基于数组的堆相比,树的指针使用了大量内存,您几乎不需要任何额外的空间,而是由值本身占用的空间.操纵这些指针也需要时间.分配和解除分配节点可能还需要一些时间和空间......
此外,无法保证树的节点将在内存中.如果两个备选方案中的任何一个都从缓存中获益,那么它就是基于数组的堆.
参考通过其他人的答案已经说过的内容，人们可能想知道为什么我们也不将数组用于 BST。二叉堆要求它应该是一棵完整的二叉树。因此，叶子节点的深度总是h或h-1。我相信正是这个特性使得使用数组非常适合二叉堆而不适合 BST（因为 BST 没有完整的二叉树要求 - 它可能是严格的/完整的/完整的）。