在 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) 时间。我有很多节点要处理，所以速度更快会很棒。

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

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

Answer 1

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

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