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

发布时间：2020-12-14 23:21:24 所属栏目：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,但随后它变得更加复杂,需要更多的内存.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!