Вставить и получить максимум из структуры за постоянное время

Question

Мне нужна структура данных для хранения положительных (не обязательно целых) значений. Он должен поддерживать следующие две операции в сублинейном времени:

1. Добавить элемент.
2. Удалить самый большой элемент.

Кроме того, самый большой ключ может масштабируйте как N ^ 2, N - количество элементов. В принципе, наличие O (N ^ 2) места не будет большой проблемой, но если существует более эффективный вариант с точки зрения хранилища, он будет работать лучше.

Я работаю в Python , поэтому, если такая структура данных существует, было бы полезно иметь реализацию на этом языке.

Answer 1

Такой структуры данных нет. Например, если бы это было так, сортировка была бы линейным временем наихудшего случая: добавьте все N элементы за O(N) время, затем удалите самый большой оставшийся элемент N раз, снова всего O(N) время.

Answer 2

лучшая структура данных, которую вы можете выбрать для этих операций, - это куча: https://www.tutorialspoint.com/python_data_structure/python_heaps.htm#: ~: text = Heap% 20is% 20a% 20special% 20tree, is% 20called% 20a% 20max% 20heap .

с этой структурой данных и добавление элемента, и удаление максимального значения равны O (log (n)).

это наиболее используемая структура данных, когда вам нужно много операций с max, например, обычно используется для реализации очередей приоритетов

Answer 3

Хотя постоянное время может быть невозможно, в зависимости от ваших входных ограничений, вы можете рассмотреть y-fast-tr ie, который имеет O(log log m) операции времени и O(n) пробел, где m - это диапазон, хотя они работают с целыми числами, используя битовую структуру. Одной из поддерживаемых операций является следующий более высокий или более низкий элемент, что позволяет отслеживать наивысший, когда последний удаляется.