前端之家收集整理的这篇文章主要介绍了
java – 为什么在实现优先级队列时使用堆而不是二叉树？，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
在我看来,堆超过二叉树的唯一优势是在二进制树中以O(1)而不是O(log(2)n)的复杂度找到堆中的最小项.
实现优先级队列时,您需要从数据结构中删除每个最小的项目.从树中删除最小的项,并且两个堆都以O(log(2)n)的复杂度完成. Althogh从树中删除项目可能更复杂.删除没有孩子的项目非常简单.
我的问题是为什么在实现优先级队列时使用堆而不是二叉树(在这种情况下更简单)？
当二叉树收敛到数组时,二进制树情况下的最坏情况复杂度为O(n),而在堆中它保持为O(log(n)).你可以使用平衡的二进制树,如红黑或AVl,但随后它变得更加复杂,需要更多的内存.
