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

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

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

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

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

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

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

If you need random insert and removal, the best way is probably a sorted array. Inserts and removals should be O(log(n)).

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

С решением, предложенным Харприт:

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

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

Харприт:

the inserts into that would be linear since you have to move items for an insert.

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

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

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

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