java – 为什么在实现优先级队列时使用堆而不是二叉树？
发布时间：2020-05-25 15:41:17 所属栏目：Java 来源：互联网
导读：在我看来,堆超过二叉树的唯一优势是在二进制树中以O(1)而不是O(log(2)n)的复杂度找到堆中的最小项. 实现优先级队列时,您需要从数据结构中删除每个最小的项目.从树中删除最小的项,并且两个堆都以O(log(2)n)的复杂度完成. Althogh从树中删除项目可能更复杂.删除
|
在我看来,堆超过二叉树的唯一优势是在二进制树中以O(1)而不是O(log(2)n)的复杂度找到堆中的最小项. 实现优先级队列时,您需要从数据结构中删除每个最小的项目.从树中删除最小的项,并且两个堆都以O(log(2)n)的复杂度完成. Althogh从树中删除项目可能更复杂.删除没有孩子的项目非常简单. 我的问题是为什么在实现优先级队列时使用堆而不是二叉树(在这种情况下更简单)？ 解决方法当二叉树收敛到数组时,二进制树情况下的最坏情况复杂度为O(n),而在堆中它保持为O(log(n)).你可以使用平衡的二进制树,如红黑或AVl,但随后它变得更加复杂,需要更多的内存.（编辑：安卓应用网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |