Как получить элемент с наименьшим ключом в коллекции за O (1) или O (log n) времени?

Question

Я знаю, что могу использовать Dictionary и получить произвольный элемент за O (1) раз.

Я знаю, что могу получить следующий самый высокий (или самый низкий) элемент за SortedDictionary за O (1) время. Но что, если я захочу удалить значение first (основанное на TKey s IComparable) в SortedDictionary?

Можно ли использовать метод .First() для получения наименьшего ключа? И в чем его сложность? Будет ли он работать в O (1), O (log n) или O (n) времени?

Является ли SortedDictionary правильной структурой данных для этого?

Примечание. Вариант использования является своего рода очередью с плохим приоритетом или упорядоченной очередью. Для этого не допускается использование открытого исходного кода (должен быть с нуля или уже в .NET 3.5 framework).

Answer 1

SortedList и SortedDictionary реализованы внутри как двоичные деревья поиска и в идеале могут дать вам производительность O (log n) в течение минимума (требует обхода дерева, но не перечисления всего списка). Однако, используя LINQ для выполнения этого Min, вероятно, будет перечислять весь список.

Я бы рассмотрел Список пропусков в качестве лучшей альтернативной структуры данных.

Answer 2

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

Answer 3

Если у вас есть SortedDictionary или SortedList, вы можете использовать .First() (или dict.Keys[0] для SortedList). В противном случае вы можете сделать:

dict[dict.Keys.Min()]

, что в целомВремя O (N) (поскольку Min () должен выполнять итерацию всей коллекции)

.First(), вероятно, будет иметь время O (1) для SortedList и O (log n) для SortedDictionary.

Для вставки и удаления используется время O (log N) для SortedDictionary и может быть до O (N) для SortedList.Обратите внимание, что если вы используете словарь для поддержки своей «очереди приоритетов», у вас не может быть двух элементов с одинаковым приоритетом.

Я не думаю, что у каждого класса есть специальная реализация для Last, поэтому есливам нужен ключ с самым высоким значением, вам, вероятно, следует использовать SortedList, поскольку вы можете сделать dict.Keys[dict.Count-1].Если вы хотите, чтобы только был наивысшим (а не наименьшим), вы можете использовать Comparer для сортировки в этом порядке и использовать First.

Answer 4

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

Answer 5

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

Answer 6

Почему бы вам не сохранить отдельный отсортированный список ключей, чтобы вы всегда могли получить элемент с наименьшим ключом, просто набрав dict[keyList[0]].