排序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

如果您正在進行最近鄰居搜索，那麼您可能需要使用k-d tree; here's a Java implementation（查看.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

檢查TreeBag從Apache Commons Collections。

TreeBag使用TreeMap來保存條目。