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 1

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)]

Answer 2

You can use OrderDict from collections. Though it is unavailable in old python versions.

from collections import OrderedDict

If you have django installed you can use django.utils.datastructures.SortedDict