在Java TreeMap中检索N个最相关的对象

Question

根据this question，我订购了Java Map，如下所示：

ValueComparator bvc =  new ValueComparator(originalMap);
Map<String,Integer> sortedMap = new TreeMap<String,Integer>(bvc);
sortedMap.putAll(originalMap);

现在，我想以top-K的方式从地图中提取K最相关的值。有没有一种高效的方法可以避免迭代映射呢？

一些类似的问题(例如，this)要求解决顶部-1的检索问题。

Answer 1

不，如果你使用Map的话就不会了。你得反复考虑一下。

你考虑过使用PriorityQueue吗？这是Java的堆实现。它具有插入任意元素和删除“最低限度”的有效操作。你可能会考虑在这里做这个。而不是Map，您可以将它们放入按关联排序的PriorityQueue中，其中最相关的作为根。然后，要提取最相关的K，只需从PriorityQueue中弹出K元素。

如果您需要类似于映射的属性(从String映射到Integer)，那么您可以编写一个类，在内部将所有东西保存在PriorityQueue和HashMap中。插入时，插入两个元素；当删除最小元素时，从PriorityQueue中弹出，然后告诉您还需要从HashMap中删除哪个元素。这仍将为您提供日志时间插入和最小删除。