Что лучше - сбалансированное двоичное дерево поиска или максимальная куча для извлечения максимального элемента?

Размышляя о структурах данных, вы должны учитывать их сложность как во времени, так и в пространстве. Здесь то же самое с пространством, поэтому давайте сосредоточимся на времени:

Сбалансированный BST:

сбалансированный BST поддерживает h = O (lg n) ⇒ все операции выполняются за время O (lg n).

Max-Heap:

Найти max O (1), удалить max O (lg n)

Это означает, что их временная сложность также одинакова.

Также, прочитав этот ответ, вы сделаете тот же вывод:

... max-heap или двоичное дерево хорошо подходят.

Однако обратите внимание, что балансировка уже созданного BST - это операция O (n) (Балансировка BST). Так что, если бы мне тоже пришлось это сделать, я бы выбрал максимальную кучу.

Для расширенного использования прочтите который структура данных, которая будет использоваться для доступа к минимальному / максимальному значению в постоянное время?

_{Источники: 1, 2.}