Как удалить максимальное значение из коллекции с 'O (log n)' _ сложностью по времени?

Question

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

Обе функции должны иметь сходные сложности, потому что они обе используются так часто.

Любая функция добавления будет простой, как O(1) и removeMax будет O (log n) или оба o (1) или один из них log n и другие o (n).

removeMax должно удалить максимальное значение и вернуть его, и должен иметь возможность использовать его несколько раз, поэтому при следующем вызове он удаляет следующее новое максимальное значение.

Есть ли способ сделать как с O (1), так и по крайней мере log n для удаления

Answer 1

Если это отсортированная структура (например, TreeSet), то для add и remove потребуется O(logN).

Если это не отсортировано, add может быть реализовано в O(1), но removeMax займет O(N), так как вы должны проверить все элементы, чтобы найти максимум в несортированной структуре данных.

Answer 2

Если вам нужна структура данных для выполнения add () и removeMax () в O (logn), то вам просто нужен отсортированный массив.Как для removeMax (), так и для add () вы можете использовать бинарный поиск, чтобы найти целевое значение.(для удаления вы найдете максимальное значение. для добавления вы найдете наибольшее значение, меньшее, чем то, которое вы хотите вставить, и вставьте значение после него). В обоих случаях сложность O (logn).

Answer 3

Макс. Кучи - это, вероятно, то, что вы ищете, их амортизируемая сложность операции remove - O (logn). Куча Фибоначчи (см. Эту отличную анимацию , чтобы увидеть, как она работает) выглядит как структура данных, подходящая для вас, поскольку она имеет O (1) для insert ивсе остальные операции.К сожалению, его реализация не является частью стандартных библиотек Java, но есть масса реализаций, которые можно найти (например, см. ответ в комментарии @Lino).

Реализация min-max кучи в Гуаве