バランスの取れたバイナリ検索ツリー、またはmax要素を抽出するための最大ヒープはどちらが良いですか？

Question

バランスBSTは、（最大要素の検索と削除の両方を抽出することを意味する）をとすると、O(log(n))の時間が最大になります。 一方、Max-heapは、最大要素を抽出するのにO(log(n))時間もかかります。

Extract-Max操作では、他の誰よりも先を見せている人はいますか？

Answer 1

データ構造を考えるときは、時間と空間の両方の複雑さを考慮する必要があります。ここではスペースは同じですが、それでは時間に焦点を当ててみましょう：

バランスBST：

バランスBSTは、H = O（LG n）を維持し、すべての操作はO（LG n）が時間で実行されます⇒。

最大ヒープ：

最大O（1）は、自分の時間の複雑さも同じであることを意味最大O（LG n）を

削除探します。

...最大ヒープまたはバイナリツリーがぴったりです。

はまた、この answerを読むことによって、あなたは同じ結論を出します。

ただし、既に構築されたBSTのバランスは、O（n）操作（Balancing a BST）であることに注意してください。だからもし私もそれをしなければならなかったら、私は最大のヒープのために行くだろう。 1、2：高度な使用方法について

は、Which data structure to use for accessing min/max in constant-time?

---

_{ソースをお読みください。}