Структура данных для быстрой вставки / удаления с сортировкой

Question

Я отчаянно ищу структуру данных, позволяющую мне выполнять большое количество вставок, почти столько же удалений (вероятно, того же порядка) и очень быстрый поиск самого высокого (или самого низкого) может соответствовать как ) значение. Удаление всегда будет влиять только на самое высокое (или, опять же, самое низкое) значение. Проблема в том, что значения должны быть отсортированы, и в любой момент я могу вставить элемент, идущий в любой точке между двумя другими. Единственное значение, которое я хочу прочитать (и удалить) быстро, в любой момент - это максимум (или, опять же, минимум).

Что-нибудь посоветуете?

Пожалуйста, дайте алгоритмический анализ сложности предложенных ответов.

Answer 1

Похоже, вам нужен Макс-куча .

Поддерживает вставку O (log n), поиск максимума O (1) и максимальное удаление O (log n).

Answer 2

Куча - это то, что вы хотите. Вот простая реализация двоичной кучи. Будь то максимальная куча или минимальная куча, зависит от функции сравнения, которую вы передаете ей: http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=789

Обратите внимание, что двоичная куча - не единственный способ построить кучу. Но, вероятно, его проще всего построить, и в большинстве случаев он работает достаточно хорошо.

Элементы в куче не отсортированы, хотя они заказаны. Единственная гарантия состоит в том, что самый высокий (самый низкий) элемент находится в верхней части кучи и будет тем, который будет получен при запросе следующего элемента.

То, что вы создаете, звучит как очередь с приоритетами . Существуют и другие способы реализации очереди с приоритетами. Например, я видел список пропущенных приоритетов , который превосходит очередь приоритетов на основе кучи.

Если вам действительно нужно вставить O (1), посмотрите на что-то вроде кучи Фибоначчи .

Answer 3

Эта структура данных называется самообалансирующимся бинарным деревом поиска , и она реализована на всех используемых мной языках, кроме Borland Pascal.
Стоимость всех упомянутых вами операций (добавление / удаление / поиск)это O(logn).Мин-макс поиск может быть O(1) тоже.

Вы можете пройти все элементы в отсортированном порядке в O(n).

edit
Я не предлагал кучу, потому что она не удовлетворяет "должны быть отсортированы" требование.

Если вам нужно вставить / удалить / посмотреть только максимум , то я бы предложил отсортированный массив или связанный список.Макс. Вставка / удаление / поиск O(1) и все элементы уже отсортированы.