java - Java中的有序可迭代高效排序结构

Question

我已经浏览了（可能几十个）StackOverflow 问题，但我认为我没有找到我想要的东西。

我想要一个具有以下属性的 Java 结构：

1. 已排序
2. 可迭代
3. 支持泛型
4. O(logn)（或更好）的插入和删除
5. O(logn)（或更好）元素访问
6. 允许重复条目

为什么？我正在实现一个 k-最近距离算法。对于数据集合中的每个点，我需要找到到第 k 个最近的其他点的距离。该算法的工作原理是遍历每对点，计算它们之间的距离，然后如果距离比该列表中的其他元素更近，则将该距离添加到每个点的最近距离的排序结构中。下面是一些代码来演示：

ArrayList<SortedThing<Double>> nearestDistances = new ArrayList<SortedThing<Double>>(numPoints);
for (int i = 0; i < numPoints; i++) {
    nearestDistances.add(new SortedThing<Double>(k));
}

for (int point = 0; point < numPoints; point++) {
    for (int otherPoint = point+1; otherPoint < numPoints; otherPoint++) {
        double distance = computeDistance(point, otherPoint);

        if (nearestDistances.get(point).size < k)
            nearestDistances.get(point).add(distance);
        else if (nearestDistances.get(point).last() > distance) {
            nearestDistances.get(point).removeLast();
            nearestDistances.get(point).add(distance);
        }

        if (nearestDistances.get(otherPoint).size < k)
            nearestDistances.get(otherPoint).add(distance);
        else if (nearestDistances.get(otherPoint).last() > distance) {
            nearestDistances.get(otherPoint).removeLast();
            nearestDistances.get(otherPoint).add(distance);
        }
    }
}

在您建议以下任何内置 Java 类之前，这就是我不想使用它们的原因：

1. PriorityQueue - 无法访问其中的最后一个元素
2. TreeSet - 不允许重复的距离
3. ArrayList - 是的，我可以使用 ArrayList，将所有 n-1 距离插入其中，在 O(nlogn) 时间内对其进行排序，然后删除第 k 个元素。但是，这将需要 O(n^2) 空间而不是 O(nk) 空间。
4. ArrayList - 或者，我可以维护一个排序的 ArrayList，删除最后一个元素并将新元素插入到正确的位置，但是每次插入需要 O(k) 时间，并且 O(logk) 找到位置插入。

有人知道这样的结构吗？我最近一直在思考这个问题，Java 没有提供任何这样的结构让我感到困惑。

Answer 1

如果您正在进行最近邻搜索，那么您可能需要使用kd 树；这是一个 Java 实现（在 .jar 文件中的 \bak 目录中查找源代码）

否则，我建议使用 TreeMap，其中值是键重复的数量（1 表示没有重复，2 表示有一个重复，等等）

Map<Key, Integer> map = new TreeMap<>();

if(map.containsKey(key)) {
    map.put(key, map.get(key) + 1);
} else {
    map.put(key, 1);
}

Answer 2

检查来自Apache Commons Collections的TreeBag。

TreeBag用于TreeMap保存条目。