堆和BST有什么区别？
何时使用堆以及何时使用BST？
如果你想以排序的方式获取元素,BST是否优于堆？
引用维基百科:
使用传统的二叉树数据结构来实现二进制堆是完全可以接受的.在添加可以通过算法解析 的元素时,在二进制堆的最后一级找到相邻元素存在问题 ...
关于这种算法如何工作的任何想法？
我无法找到有关此问题的任何信息,因为大多数二进制堆都是使用数组实现的.
任何帮助赞赏.
最近,我注册了一个OpenID帐户,无法编辑我的初始帖子或评论答案.这就是我通过这个答案回应的原因.非常遗憾.
引用米奇小麦:
@Yse:你的问题是"如何找到二进制堆的最后一个元素"？
是的.或者更确切地说,我的问题是:"我如何找到非基于数组的二进制堆的最后一个元素？".
引用Suppressingfire:
你有没有提出这个问题的背景？(也就是说,你试图解决一些具体问题吗？)
如上所述,我想知道"找到非基于数组的二进制堆的最后一个元素"的好方法,这是插入和删除节点所必需的.
引用罗伊:
对我来说,使用普通的二叉树结构(使用定义为[data,pLeftChild,pRightChild]的pRoot和Node)并添加两个额外的指针(pInsertionNode和pLastNode)似乎是最容易理解的.pInsertionNode和pLastNode都将在插入和删除子例程期间更新,以便在结构中的数据发生更改时保持当前状态.这使O(1)访问结构的插入点和最后一个节点.
是的,这应该有效.如果我没有弄错,找到插入节点和最后一个节点,当它们的位置由于删除/插入而变为另一个子树时,可能会有点棘手.但我会试一试.
引用Zach Scrivena:
如何进行深度优先搜索......
是的,这将是一个很好的方法.我也会尝试一下.
我还在想,如果有办法"计算"最后一个节点和插入点的位置.具有N个节点的二进制堆的高度可以通过获取大于N的最小二次幂的log(基数2)来计算.也许可以计算最深级别上的节点数.然后可能确定如何遍历堆以到达插入点或节点以进行删除.