在Map中查找最小值的有效方法

Question

我试图找到key最小值,Map如下所示.

 Map<Node, Integer> freeMap = new TreeMap<>();
 Node minNode = null;
        for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) {
            if (minNode == null) {
                minNode = entry.getKey();
            } else {
                if (entry.getValue() < freeMap.get(minNode)) {
                    minNode = entry.getKey();
                }
            }
        }

首先,是否有一种直接的方法来找到key最小的value比使用foreach循环.其次,你能否提出一些可用于存储Node对象和相关Integer值的备用数据结构方法,因此我可以entry在恒定时间O(1)中以最小值获取.

Answer 1

O(1) Min 的数据结构 对于替代数据结构，优先级队列怎么样。

您可以使用自定义比较器或让您的数据类型实现Comparable。

来自javadoc：

实现说明：此实现为入队和出队方法（offer、poll、remove() 和 add）提供了 O(log(n)) 时间；remove(Object) 和 contains(Object) 方法的线性时间；以及检索方法（查看、元素和大小）的恒定时间。

O(1) Min 和摊销 O(1) 查找的数据结构

如果您想要高效的 min 和高效的 find，并且您可以控制对数据结构的访问（否则问题的重点是什么？），您可以通过扩展 Java 的 HashMap 来跟踪最小元素来推出您自己的 HashMap。

您必须重写put,putAll和remove方法。在每种情况下，您都可以只调用超类方法（例如super.put(key, value)），然后更新最小元素，该元素将作为新定义的类的实例成员保留。

请注意，这会将删除时间增加到 (O(N))（因为您必须更新最小值）。