3

I'm currently trying to figure out which data structure might be the best one to use. So here is what I am trying to do:

I have an object and a value associated with this object. I want to be able to know which entry in the structure has the smallest value.

So for example if I have the following objects:

 ZebraObject, 10
 CowObject, 1
 DogObject, 2

I want to be able to know which object has the smallest value (which in this case, is CowObject). I'll also have to access the data inside the CowObject (call some functions, do some calculation etc) and at the end, I'll be doing something like 'value += value'. So after I've accessed the CowObject, the data will look like

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

Can anyone help me figure out what the best data structure for this situation?

Edit: I'm assuming that every elements (at least for the object), are unique. The float value associated with the object can be duplicates.

dwnenr
  • 443
  • 1
  • 4
  • 15
  • 1
    It seems like you need a min heap. In this case you minimum object will be on top of the heap and it will take O(1) time to get its value – Serhiy Chupryk Oct 06 '15 at 05:34
  • I totally forgot about the min heap!! Thank you very much!! – dwnenr Oct 06 '15 at 05:36
  • @SerhiyChupryk, according to your suggestion, values 1,2,10 will be considered as keys and minheap would be ideal, but currently the OP is trying to consider modifying these keys over time and would contain duplicate keys. Oh yes, min/max heaps can contain duplicates. My thought process in the beginning considered ZebraObject, CowObject, DogObject to be keys and 10,1,2 to be values. I should have thought the other way. (Thanks for pointing out minheap) – a3.14_Infinity Oct 06 '15 at 05:40
  • Have you come across `SortedSet`? – tomab Oct 06 '15 at 05:45
  • @tomab I just checked it out. But it seems inorder for me to use SortedSet, I'll need to make the float value a member of the Object. – dwnenr Oct 06 '15 at 06:20
  • If this is your only concern, you can solve it by creating a class which base its methods and behavior on `SortedSet` but uses an `Object` and a `float`. The idea is to rely on some class which already exists, rather than creating from scratch your own `MinHeap`-like implemention. – tomab Oct 06 '15 at 06:24

2 Answers2

0

Sorted Set is helpful to fulfill your requirement. But sorted set not allow duplicates. For sorting depending on specific field of object Implement IComparer.

you may get more help from SortedSet and equality

Community
  • 1
  • 1
Pankaj Saboo
  • 1,125
  • 1
  • 8
  • 27
  • a sorted set does way to much here ;) – Random Dev Oct 06 '15 at 05:58
  • Looking at the SortedSet on msdn, it seems like I need to keep the float value as a member of the object class. Is there a way to keep these 2 seperated? – dwnenr Oct 06 '15 at 06:14
  • means you want to keep keep if this then you may use – Pankaj Saboo Oct 06 '15 at 06:27
  • Yes, I would like to keep it as or even . I just need to be able to access both data and modify them as well. – dwnenr Oct 06 '15 at 06:29
  • means you want to keep keep if this then you may use Dictionary or List>. Refer following links 1) http://stackoverflow.com/questions/289/how-do-you-sort-a-dictionary-by-value 2) http://www.c-sharpcorner.com/UploadFile/mahesh/sort-a-dictionary-by-value-in-C-Sharp/ – Pankaj Saboo Oct 06 '15 at 06:37
0

ObservableCollection is the best way if you will bind to the list. it already implements the INotifyPropertyChanged interface. Maybe make your Viewmodel inherit from the observablecollection

Matthias Herrmann
  • 2,650
  • 5
  • 32
  • 66