Python data structure for sorted key-value pairs
Question: I have a (fixed) set of keys for which I store a value. I often look up the
value for a key and increment or decrement it. A typical dict usage.

    
    
    x = {'a': 1, 'b': 4, 'c': 3}
    x['a'] += 1
    

Additionally however, just as often as incrementing or decrementing values, I
also need to know the key for the i-th largest (or smallest) value. Of course
I can do the sorting:

    
    
    s = sorted(x, key=lambda k:(x[k],k))
    s[1] == 'c'
    

The problem is sorting every time seems rather expensive. Especially because I
only increment one item in between sorts. I feel that I could use another data
structure better suited for this. A tree perhaps?


Answer: You could use blist's sorteddict to keep the values in order. Here's a quick
implementation of a dictionary which, when iterated over, returns its keys in
order of its values (not really tested intensively):

    
    
    import collections
    from blist import sorteddict
    
    class ValueSortedDict(collections.MutableMapping):
        def __init__(self, data):
            self._dict = {}
            self._sorted = sorteddict()
            self.update(data)
    
        def __getitem__(self, key):
            return self._dict[key]
    
        def __setitem__(self, key, value):
            # remove old value from sorted dictionary
            if key in self._dict:
                self.__delitem__(key)
            # update structure with new value
            self._dict[key] = value
            try:
                keys = self._sorted[value]
            except KeyError:
                self._sorted[value] = set([key])
            else:
                keys.add(key)            
    
        def __delitem__(self, key):
            value = self._dict.pop(key)
            keys = self._sorted[value]
            keys.remove(key)
            if not keys:
                del self._sorted[value]
    
        def __iter__(self):
            for value, keys in self._sorted.items():
                for key in keys:
                    yield key
    
        def __len__(self):
            return len(self._dict)
    
    x = ValueSortedDict(dict(a=1, b=4, c=3))
    x['a'] += 1
    print list(x.items())
    x['a'] += 10
    print list(x.items())
    x['d'] = 4
    print list(x.items())
    

This gives:

    
    
    [('a', 2), ('c', 3), ('b', 4)]
    [('c', 3), ('b', 4), ('a', 12)]
    [('c', 3), ('b', 4), ('d', 4), ('a', 12)]
    

