为什么在实现优先级队列时使用堆而不是二叉树？ [英] Why use heap instead of binary tree when implementing priority queue?
问题描述
在我看来，堆二进制树的唯一优势是在O（1）而不是O（log（2）n）的复杂度中找到堆中最小的项。
It seems to me that the only advantage of heap over binary tree is to find the smallest item in the heap in complexity of O(1) instead of O(log(2)n) in binary tree.
当实现优先级队列时，您需要从数据结构中删除最小的项目。从树中删除最小项，并且以O（log（2）n）的复杂度完成堆。从树中删除项可能更复杂。
When implementing priority queue you need to delete the smallest item each from the data structre. deleting the smallest item from a tree and both heap done in complexity of O(log(2)n). Althogh deleting item from a tree may be more complex. Deleting item with no childrens acctually very simple.
我的问题是为什么在实现优先级队列时使用堆而不是二叉树（在这种情况下更简单）？
My question is why use heap instead of binary tree(which is simpler in this case) when implementing priority queue?
推荐答案
二进制树的最坏情况下的复杂度为O（n），当二进制树收敛到数组时， log（n））。你可以使用平衡的二叉树像红黑或AVl，但随后它变得更加复杂，需要更多的内存。
Worst case complexity in case of binary tree will be O(n) when binary tree converges to an array while in heap it remains O(log(n)). you can use balanced binary trees like red black or AVl but then it wud become more complex and would require more memory.
这篇关于为什么在实现优先级队列时使用堆而不是二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
