最适合支持排序的数据结构是什么？

Question

我目前正在尝试确定哪种数据结构最适合使用。因此，这是我要做的事情：

我有一个对象和与该对象关联的值。我想知道在结构中哪个条目具有最小值。

例如，如果我有以下对象：

 ZebraObject, 10
 CowObject, 1
 DogObject, 2

我希望能够知道哪个对象的值最小（在这种情况下，是CowObject）。我还需要访问CowObject内部的数据（调用一些函数，进行一些计算等），最后，我将执行类似于'value += value'的操作。因此，在我访问了CowObject之后，数据会变成这样

 ZebraObject, 10
 CowObject, 2 // (1 + 1)
 DogObject, 2

有人能帮我找出这种情况下最好的数据结构吗？

编辑：我假设每个元素（至少对于该对象）都是唯一的。与对象相关联的浮点值可能重复。

- dwnenr

---

看起来你需要一个最小堆。在这种情况下，你的最小对象将位于堆的顶部，并且获取其值只需要O(1)时间。 - Serhiy Chupryk

我完全忘记了最小堆！！非常感谢！！ - dwnenr

根据@SerhiyChupryk的建议，值1、2、10将被视为键，并且最小堆将是理想的选择，但目前OP正在尝试考虑随时间修改这些键，并且会包含重复的键。是的，最小/最大堆可以包含重复项。我一开始的思路是将ZebraObject、CowObject、DogObject视为键，而10、1、2视为值。我应该换个角度思考。（感谢指出最小堆） - a3.14_Infinity

你是否遇到过 SortedSet<T>？ - tomab

@tomab，我刚刚查看了一下。但是似乎为了使用SortedSet，我需要将浮点值作为对象的成员。 - dwnenr

如果这是您唯一的关注点，您可以通过创建一个类来解决它，该类基于 SortedSet<T> 的方法和行为，但使用了一个 Object 和一个 float。这个想法是依赖于已经存在的某些类，而不是从头开始创建自己的类似于 MinHeap 的实现。 - tomab

Answer 1

Sorted Set（排序集合）可以帮助您满足需求。但是排序集合不允许重复项。如果要根据对象的特定字段进行排序，请实现IComparer接口。

您可以从SortedSet和相等性中获得更多帮助。

- Pankaj Saboo

---

一个排序集在这里做了太多的事情 ;) - Random Dev

看了一下 MSDN 上的 SortedSet，似乎我需要将浮点值作为对象类的成员保留。有没有办法将这两个分开保留？ - dwnenr

如果你想保留 <object,value>，那么你可以使用“means you want to keep keep if this then you may use”。 - Pankaj Saboo

是的，我想保持它为<object, value>甚至<value, object>。我只需要能够访问并修改这两个数据。 - dwnenr

如果你想保留 <object,value>，那么你可以使用字典或者List<KeyValuePair<Object,value>>。请参考以下链接：1) https://dev59.com/93VD5IYBdhLWcg3wXaid 2) http://www.c-sharpcorner.com/UploadFile/mahesh/sort-a-dictionary-by-value-in-C-Sharp/ - Pankaj Saboo

Answer 2

如果您要绑定到列表，ObservableCollection是最好的方法。它已经实现了INotifyPropertyChanged接口。也许可以让您的ViewModel从ObservableCollection继承。

- Matthias Herrmann