>我目前正在学习数据结构并尝试实现BST和max-heap(使用BST作为基类)。但我意外地发现似乎不可能从 BST 中得出堆。几乎所有堆的实现都基于数组,而不是使用指向左右的指针,并且大多数BST都基于指针而不是数组。
所以我的问题是为什么我必须使用数组来实现堆?而且,在实现BST时,为什么人们选择使用指向左侧和右侧的指针而不是数组?我知道使用数组来实现BST可能会花费更多空间,并且更难实现删除功能,还有更多原因吗?
非常感谢!
二进制堆的标准实现使用数组完成的主要原因是因为堆是完整的二叉树。
因为完整的二叉树总是逐级增长(意思是:首先父级将被节点填充,然后才填充子级)。
因此,我们能够使用数组,其中对于位置 i
的节点,在位置 2*i
找到左子节点,在位置 2*i+1
找到右子节点。
指针而不是数组实现的原因是二叉搜索树不能保证是完整的二叉树