数组实现BST，链表实现堆

Question

我目前正在学习数据结构，并试图实现BST和max堆(使用BST作为基类)。但是我无意中发现从BST派生堆似乎是不可能的。堆的几乎所有实现都是基于数组，而不是使用指向左和右的指针，而大多数BST是基于指针而不是数组的。

那么，我的问题是为什么我必须使用数组来实现堆呢？在实现BST的过程中，人们为什么选择使用指向左和右的指针，而不是数组？我知道使用数组来实现BST可能会花费更多的空间，而且很难实现删除功能，还有更多的原因吗？

非常感谢!

Answer 1

使用数组完成二进制堆的标准实现的主要原因是，因为堆是完整的二叉树。

因为完整的二叉树总是一层一层地生长(意思是:首先，父级将填充节点，然后才填充子级别)。

因此，我们可以使用数组，其中对于位置i的节点，在2*i位置找到左子节点，在2*i+1位置找到右子节点。

使用指针而不使用数组实现二进制搜索树的原因是，二进制搜索树不一定是完整的二叉树。