python - 在 O(1) 时间 Python 中查找字典中的最小值

Question

我需要一种方法在 O(1) 时间或任何次线性时间(如果可能的话)内找到充满 Node 对象的字典中的最小值。

这是我需要的示例:

'''
 Nodes have 4 attributes: 
  - stack
  - backwards
  - forwards
  - total_score
'''
dict = {str(Node1.stack): Node1, 
        str(Node2.stack): Node2, ... } # note that keys are the stacks as strings

key, smallest = min(frontier.items(), key=lambda pair: pair[1].total_score)
( ^^^ something better than this! ^^^ )

上面的最后一行(关键，最小...)是我目前所拥有的。它工作正常，但它太慢了。我在网上看到 min() 函数需要 O(n) 时间。我有很多节点要处理，所以更快的东西会很棒。

edit 之前应该提到过，但这是在 A* 算法中运行的 - 边界是动态更新的。我需要能够做的操作是:

1. 在 O(1) 中找到最小值，或者至少 < O(n)
2. 快速更新特定元素的值
3. 轻松访问属性

Answer 1

不可能在 O(1) 时间内从字典中获取最小值，因为您必须检查每个值。但是，如果将数据存储在堆或排序树中(其中数据按值排序)，则可以进行快速查找。树通常为您提供 O(log n) 的插入和搜索时间。

如果您实际上只需要数据的最小值而您永远不需要查找其他值，您可以只创建一个 minValue 变量，每次插入或删除项目。