哪一個更適合平衡二叉搜索樹或提取最大元素的最大堆？

由於平衡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

我認爲平衡樹是一個開銷。現在我並不擔心實施的簡單性。 –

回答