Which one is better balanced binary search tree or maximum heap for extracting max element?

Question

Since balanced BSTwill take O(log(n))time, it will extract max (by extraction, I mean both the find element and delete Max) . On the other hand, it Max-heapalso takes time O(log(n))to extract the maximum element.

Do any of them have an advantage over the other in the Extract-Max operation?

Answer 1

When you think about data structures, you must consider their complexity, both time and space. The space here is the same, so let's focus on time:

Balanced BST:

balanced BST supports h = O (log n) ⇒ all operations are performed in O (log n) time.

Max-heap

Find max O (1), Delete max O (log n)

which means that their time difficulties also coincide.

Also, after reading this answer , you will draw the same conclusion:

... a max heap or binary tree works well.

However, note that balancing an already constructed BST is an O (n) operation ( Balancing a BST ). Therefore, if I did this too, I would choose the maximum heap.

min/max ?

---

_{: 1, 2. >}