Какую родовую коллекцию я должен выбрать в C# для поддержания отсортированного «списка»

Question

У меня есть класс Node, который имеет свойство float Distance.

Мне нужна структура данных, которую я могу разместить внутри всех моих узлов, и они будут отсортированы (например, в дереве AVL или Red Black Tree).

• Я хочу, чтобы вставить в O (журнал (п))
• Я хочу, чтобы извлечь и удалить минимум в O (журнал (п))

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

Использование списка и сортировки я из вопроса, так как удаление (O (п)) и найти минимальное также (O (п))

Все мне нужно, это простой общий красный черный древовидная структура, которая будет Сортировка по некоторому предикату, который я предоставил (чтобы сравнить расстояние внутри узла)

Есть ли такая структура данных в BCL?

Answer 1

Вы хотите использовать класс библиотеки c5 Collections Library TreeBag<T>. Это красно-черное дерево, которое позволяет дублировать (отсюда сумка, а не комплект). доступ по индексу значения элемента - O (log n); вставка и удаление O (log n) амортизируются.

Библиотека C5 Collection финансировалась Microsoft; он с открытым исходным кодом и доступен gratis. Цена правильная.

http://www.itu.dk/research/c5/

Answer 2

Другим вариантом является skip list. .NET Framework не имеет одного, но я реализовал один в C# некоторое время назад. См. A More Memory-Efficient Skip List.

В списке пропусков есть вставка, поиск и удаление O (log n), а O (1) удаление верхнего элемента.

Если вы хотите кучу, см. A Generic Binary Heap Class.

Answer 3

На самом деле, для этого вы можете использовать SortedDictionary. Но то, что вам нужно (при условии, что расстояние int) является SortedDictionary<int, List<Item>>.

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

Чтобы удалить наименьший предмет, найдите List с помощью самого маленького ключа и удалите из него предмет. Если List пуст, удалите его из словаря.

С удалением от начала в List неэффективно, вам нужно будет либо удалить с конца List (в результате LIFO порядка для элементов с одинаковым ключом), или использовать Queue вместо List.

Это, вероятно, не самое эффективное решение, но вставка, поиск наименьшего элемента и удаление наименьшего элемента - все O (log n).