python - Data structure to store key-value pairs and retrive the key for the lowest value quickly -

I'm implementing something like a cache, which works like this:

1. If the new value for the given key comes from some external process, stores that value, and remembers the time when this value is reached.
2. If we are useless, get the oldest entry in the cache, get a new value, update the key and cache from external source.
3. When prompted, return the value for the given key.

I need a data structure to store a key-value pair, will allow the following tasks to be performed as low as possible (in order of speed priority) ):

1. Find the key with the lowest (unknown) value.
2. Update if the key is not present, add value for a given key or a new key-value pair.
3. Other regular hash-table actions, such as deleting a key, whether a key exists or not, etc.

Do any data structures allow this? The problem here is that I need to have some pricing orders to expedite the first query and I need to give some important order to update the prices for the given key. I have the most till now Good solution is something like this:

The store has a regular hashtable value and a pair of value (value, key) in the form of a value-ordered pile. Finding the key for the lowest value is like this:

1. Find the key for the lowest value on the heap.
2. Find the value for that key from the hashtable. / Li>
3. If the value does not pop the value from a heap and repeats it from step 1.

Updating prices goes like this:

1. Store the value in the hashtable.
2. Push the new (value, key) pair to the pile.

Delete a key is more difficult and needs to be searched for the value in the heap gives it something like O (log n) display, but this solution seems to be cumbersome for me it happens.

Are there any data structures that combine a heap of keys for the hashtable properties and associated values? I am programming in Python, so if there is an existing implementation in Python, then this is a big plus.