Как мне эффективно отслеживать самый маленький элемент в коллекции?

Question

В духе вопросы по программированию:предположим, существует коллекция объектов, которые можно сравнить друг с другом и отсортировать.Какой наиболее эффективный способ отслеживать наименьший элемент в коллекции по мере добавления объектов, а текущий наименьший иногда удаляется?

Answer 1

Использование мини-кучи - лучший способ.

http://en.wikipedia.org/wiki/Heap_(data_structure)

Он создан специально для этого приложения.

Answer 2

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

Answer 3

@Харприт
Это не оптимально.Когда объект удаляется, эриксону придется просканировать всю коллекцию, чтобы найти новый самый маленький.

Вы хотите почитать о Бинарное дерево поискас.MS имеет хороший Сайт чтобы начать спускаться по тропинке.Но, возможно, вы захотите приобрести такую книгу, как Введение в алгоритмы (Кормен, Лейзерсон, Ривест, Штайн) если вы хотите глубоко погрузиться.

Answer 4

Для случайного удаления куча Фибоначчи даже быстрее, чем минимальная куча. Вставка - это O (1), а нахождение мин - также O (1). Удаление - это O (log (n))

Answer 5

Если вам нужна случайная вставка и удаление, вероятно, лучшим способом является сортированный массив.Вставки и удаления должны быть O(log(n)).

Да, но вам нужно будет повторно сортировать при каждой вставке и (возможно) при каждом удалении, которое, как вы заявили, равно O (log (n)).

С помощью решения, предложенного Харпри:

• у вас есть один O (n) проход в начале, чтобы найти наименьший элемент
• после этого выполняется O (1) вставок (требуется только 1 сравнение с уже известным наименьшим элементом).
• удалениями будет O (n), потому что вам нужно будет повторно найти наименьший элемент (имейте в виду, что обозначение Big O - наихудший случай).Вы также могли бы оптимизировать, проверив, является ли элемент, подлежащий удалению, (известным) наименьшим, и если нет, просто не выполняйте никаких повторных проверок, чтобы найти наименьший элемент.

Итак, это зависит от обстоятельств.Один из этих алгоритмов будет лучше для варианта использования с большим количеством вставок и небольшим количеством удалений, но другой в целом более последователен.Я думаю, что я бы по умолчанию использовал механизм Харприта, если бы не знал, что наименьшее число будет удаляться часто, потому что это выявляет слабое место в этом алгоритме.

Answer 6

Харприт:

вставки в это были бы линейными, так как вам нужно перемещать элементы для вставки.

Разве это не зависит от реализации коллекции?Если он действует как связанный список, inserts будет равен O (1), в то время как если бы он был реализован как массив, он был бы линейным, как вы указали.

Answer 7

Зависит от того, какие операции должен поддерживать ваш контейнер. min-heap - лучший вариант, если вам может потребоваться удалить элемент min в в любой момент времени, хотя некоторые операции нетривиальны (в некоторых случаях амортизируется log (n) время).

Однако, если вам нужно только нажать / выскочить спереди / сзади, вы можете просто использовать миндек, который достигает амортизированного постоянного времени для всех операций (включая findmin). Вы можете поиск scholar.google.com узнать больше об этой структуре. Недавно мы с другом сотрудничали, чтобы создать гораздо более понятную и удобную для реализации версию минидека. Если это то, что вы ищете, я могу опубликовать детали для вас.