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

Question

我正在实现类似缓存的东西，其工作原理如下:

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

我需要一个数据结构来存储键值对，以便尽快执行以下操作(按速度优先顺序):

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

是否有任何数据结构允许这样做？这里的问题是，要快速执行第一个查询，我需要按值排序的内容，并且要快速更新给定键的值，我需要按键排序的内容。到目前为止我拥有的最好的解决方案是这样的:

将值存储在常规哈希表中，并将(值，键)对存储为值排序堆。查找最低值的键如下所示:

1. 查找堆上最低值的键。
2. 从哈希表中查找该键的值。
3. 如果值不匹配，则从堆中弹出该值并从步骤 1 开始重复。

更新值的过程如下:

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

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

是否有任何数据结构结合了键的哈希表和关联值的堆的属性？我正在使用 Python 进行编程，因此如果 Python 中有现有的实现，那就是一个很大的优势。

Answer 1

大多数堆实现都会在 O(1) 时间内获得集合中最低的键，但无法保证随机查找或删除的速度。我建议将两种数据结构配对:任何简单的堆实现和任何开箱即用的哈希表。

当然，任何平衡二叉树都可以用作堆，因为最小值和最大值分别位于最左边和最右边的叶子上。红黑树或 AVL 树应该为您提供 O(lg n) 堆和字典操作。