Как мне эффективно отслеживать самый маленький элемент в коллекции?
-
09-06-2019 - |
Вопрос
В духе вопросы по программированию:предположим, существует коллекция объектов, которые можно сравнить друг с другом и отсортировать.Какой наиболее эффективный способ отслеживать наименьший элемент в коллекции по мере добавления объектов, а текущий наименьший иногда удаляется?
Решение
Использование мини-кучи - лучший способ.
http://en.wikipedia.org/wiki/Heap_(data_structure)а> р>
Он создан специально для этого приложения.
Другие советы
Если вам нужна случайная вставка и удаление, лучше всего использовать отсортированный массив. Вставки и удаления должны быть O (log (n)). Р>
@Харприт
Это не оптимально.Когда объект удаляется, эриксону придется просканировать всю коллекцию, чтобы найти новый самый маленький.
Вы хотите почитать о Бинарное дерево поискас.MS имеет хороший Сайт чтобы начать спускаться по тропинке.Но, возможно, вы захотите приобрести такую книгу, как Введение в алгоритмы (Кормен, Лейзерсон, Ривест, Штайн) если вы хотите глубоко погрузиться.
Для случайного удаления куча Фибоначчи даже быстрее, чем минимальная куча. Вставка - это O (1), а нахождение мин - также O (1). Удаление - это O (log (n))
Если вам нужна случайная вставка и удаление, вероятно, лучшим способом является сортированный массив.Вставки и удаления должны быть O(log(n)).
Да, но вам нужно будет повторно сортировать при каждой вставке и (возможно) при каждом удалении, которое, как вы заявили, равно O (log (n)).
С помощью решения, предложенного Харпри:
- у вас есть один O (n) проход в начале, чтобы найти наименьший элемент
- после этого выполняется O (1) вставок (требуется только 1 сравнение с уже известным наименьшим элементом).
- удалениями будет O (n), потому что вам нужно будет повторно найти наименьший элемент (имейте в виду, что обозначение Big O - наихудший случай).Вы также могли бы оптимизировать, проверив, является ли элемент, подлежащий удалению, (известным) наименьшим, и если нет, просто не выполняйте никаких повторных проверок, чтобы найти наименьший элемент.
Итак, это зависит от обстоятельств.Один из этих алгоритмов будет лучше для варианта использования с большим количеством вставок и небольшим количеством удалений, но другой в целом более последователен.Я думаю, что я бы по умолчанию использовал механизм Харприта, если бы не знал, что наименьшее число будет удаляться часто, потому что это выявляет слабое место в этом алгоритме.
Харприт:
вставки в это были бы линейными, так как вам нужно перемещать элементы для вставки.
Разве это не зависит от реализации коллекции?Если он действует как связанный список, inserts будет равен O (1), в то время как если бы он был реализован как массив, он был бы линейным, как вы указали.
Зависит от того, какие операции должен поддерживать ваш контейнер. min-heap - лучший вариант, если вам может потребоваться удалить элемент min в в любой момент времени, хотя некоторые операции нетривиальны (в некоторых случаях амортизируется log (n) время).
Однако, если вам нужно только нажать / выскочить спереди / сзади, вы можете просто использовать миндек, который достигает амортизированного постоянного времени для всех операций (включая findmin). Вы можете поиск scholar.google.com узнать больше об этой структуре. Недавно мы с другом сотрудничали, чтобы создать гораздо более понятную и удобную для реализации версию минидека. Если это то, что вы ищете, я могу опубликовать детали для вас.