哪一个更适合平衡二叉搜索树或提取最大元素的最大堆?
由于平衡BST
将采取O(log(n))
时间正在提取最大(通过提取我的意思是既查找和删除最大元素)。 另一方面Max-heap
也需要O(log(n))
时间来提取最大元素。哪一个更适合平衡二叉搜索树或提取最大元素的最大堆?
他们中的任何一个在Extract-Max操作中都有优势吗?
在考虑数据结构时,应该考虑到它们在时间和空间上的复杂性。这里的空间是相同的,所以让我们集中时间:
平衡BST:
平衡BST维持H = O(LG N)⇒所有操作在O(LG n)的时间运行。
最大堆:
查找最大O(1),删除最大O(LG n)的
这意味着它们的时间复杂度也相同。
而且通过阅读这篇answer,你得出同样的结论:
...一个最大堆或二叉树是一个不错的选择。
但是,请注意,平衡已经构建的BST是O(n)操作(Balancing a BST)。所以,如果我也必须这样做,那么我会去做一个最大的堆。
对于高级用法,看Which data structure to use for accessing min/max in constant-time?
那么你对此有何结论? –
因此,对于这种操作,在效率方面都很好。如果我是你,我会看到哪个更容易实现,或者我是否可以访问提供这种数据结构的库。例如,如果我在[tag:C++]中编写,并且有一个我喜欢的库,它提供了一个堆,我会为此付出! – gsamaras
我认为平衡树是一个开销。现在我并不担心实施的简单性。 –
我知道。但是如果我们想要执行提取最大操作。那么哪一个将是合适的数据结构,一个平衡的bst或max堆。 –
在某些特殊情况下,'BST'只会比'Heap'多一个操作,否则两个操作都可以提取最大值。但是多一个操作是微不足道的。 –
@GAURANGVYAS找到平衡Bst的最右边节点将采取O(log(n))并执行删除操作将花费O(1)。 –