哪一个更适合平衡二叉搜索树或提取最大元素的最大堆？

由于平衡BST将采取O(log(n))时间正在提取最大（通过提取我的意思是既查找和删除最大元素）。另一方面Max-heap也需要O(log(n))时间来提取最大元素。哪一个更适合平衡二叉搜索树或提取最大元素的最大堆？

他们中的任何一个在Extract-Max操作中都有优势吗？

我知道。但是如果我们想要执行提取最大操作。那么哪一个将是合适的数据结构，一个平衡的bst或max堆。 –

在某些特殊情况下，'BST'只会比'Heap'多一个操作，否则两个操作都可以提取最大值。但是多一个操作是微不足道的。 –

@GAURANGVYAS找到平衡Bst的最右边节点将采取O（log（n））并执行删除操作将花费O（1）。 –

在考虑数据结构时，应该考虑到它们在时间和空间上的复杂性。这里的空间是相同的，所以让我们集中时间：

平衡BST：

平衡BST维持H = O（LG N）⇒所有操作在O（LG n）的时间运行。

最大堆：

查找最大O（1），删除最大O（LG n）的

这意味着它们的时间复杂度也相同。

而且通过阅读这篇answer，你得出同样的结论：

...一个最大堆或二叉树是一个不错的选择。

但是，请注意，平衡已经构建的BST是O（n）操作（Balancing a BST）。所以，如果我也必须这样做，那么我会去做一个最大的堆。

_{来源：1，2。}

2017-05-09 13:38:01 gsamaras

那么你对此有何结论？ –

因此，对于这种操作，在效率方面都很好。如果我是你，我会看到哪个更容易实现，或者我是否可以访问提供这种数据结构的库。例如，如果我在[tag：C++]中编写，并且有一个我喜欢的库，它提供了一个堆，我会为此付出！ – gsamaras

我认为平衡树是一个开销。现在我并不担心实施的简单性。 –

回答