用于存储键值对并快速检索最小值的键的数据结构

我正在实现类似缓存这样的功能:

1. 如果给定键的新值来自某个外部进程,请存储该值,并记住该值到达的时间。
2. 如果空闲,请在缓存中找到最旧的条目,从外部源获取该键的新值并更新缓存。
3. 请求时返回给定键的值。

我需要一个数据结构来存储键值对,它允许尽可能快地执行以下操作(按速度优先顺序):

1. 查找具有最低(未知)值的键。
2. 更新给定键的值,如果键不存在,则添加新的键值对。
3. 其他常规哈希表操作,如删除键、检查键是否存在等。

是否有数据结构允许这样做?这里的问题是,为了快速执行第一个查询,我需要排序的值,为了快速更新给定键的值,我需要排序的键。到目前为止,我拥有的最佳解决方案是这样的:

将值存储在常规哈希表中,将成对的(值、键)存储为值顺序堆。查找最小值的键如下所示:

1. 查找堆中最小值的键。
2. 从哈希表中查找该键的值。
3. 如果值不匹配,则从堆中弹出值,然后从步骤1中重复。

更新值的过程如下:

1. 将值存储在哈希表中。
2. 将新的(值、键)对推送到堆中。

删除键更复杂,需要在堆中搜索值。这提供了类似O(log n)的性能,但这个解决方案对我来说似乎很麻烦。

是否有任何数据结构组合键的哈希表属性和关联值的堆属性?我正在用python编程,所以如果在python中有现有的实现,这是一个很大的优势。