java – 为什么在实现优先级队列时使用堆而不是二叉树?

前端之家收集整理的这篇文章主要介绍了java – 为什么在实现优先级队列时使用堆而不是二叉树?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
在我看来,堆超过二叉树的唯一优势是在二进制树中以O(1)而不是O(log(2)n)的复杂度找到堆中的最小项.

实现优先级队列时,您需要从数据结构中删除每个最小的项目.从树中删除最小的项,并且两个堆都以O(log(2)n)的复杂度完成. Althogh从树中删除项目可能更复杂.删除没有孩子的项目非常简单.

我的问题是为什么在实现优先级队列时使用堆而不是二叉树(在这种情况下更简单)?

解决方法

当二叉树收敛到数组时,二进制树情况下的最坏情况复杂度为O(n),而在堆中它保持为O(log(n)).你可以使用平衡的二进制树,如红黑或AVl,但随后它变得更加复杂,需要更多的内存.
原文链接:https://www.f2er.com/java/127652.html

猜你在找的Java相关文章