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

Question

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

Answer 1

Лучше всего использовать min-heap.

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

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

Answer 2

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

Answer 3

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

Вы хотите прочитать о Двоичном дереве поиска . У MS есть хороший сайт , чтобы начать путь. Но вы можете получить книгу типа Введение в алгоритмы (Cormen, Leiserson, Rivest, Stein) , если вы хотите глубоко погрузиться.

Answer 4

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

Answer 5

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

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

Answer 6

Harpreet:

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

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

Answer 7

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

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

С решением, предложенным Harpreet:

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

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