Карта, отсортированная по размеру коллекции значений

Question

Я пытаюсь сортировать карту Map<Integer,Set<Integer>>, которая хранит элементы, отсортированные по size() установленного значения.

На практике это карта узла с другими узлами, подключенными к этому узлу. Я хочу быстро (O (logn)) получить доступ к узлу с наибольшим количеством ребер без необходимости сортировать каждый раз.

Например, порядок должен быть:

3 => {1,2,4,5} 
12 => {1,2,3} 
14 => {3,2,3} 
65 => {3,8} 
6 => {2} 
2 => {5} 

С TreeMap не будет делать это, так как я не могу сортировать на основе значений, я, вероятно, нужно свернуть что-то обычай.

EDIT: Размер набора действительно может измениться, которые могут чрезмерно усложнять еще больше

Что бы самый простой способ для достижения этой цели?

Answer 1

Вот пример сортировки, как использовать два набора для этого. Один набор сортируется по Set :: size, а другой - это обычная карта с индексом integer. Чтобы использовать это, вы должны хранить одни и те же пары ключ/значение на обеих картах.

Я не уверен, рекомендую ли я попытаться сделать одну карту из этого. У него есть два поиска по индексу и по размеру, поэтому он не работает как обычная карта. Это будет зависеть от вашей модели использования.

package quicktest; 

import static java.util.Comparator.comparing; 
import java.util.HashSet; 
import java.util.Set; 
import java.util.TreeMap; 

public class TreeMapTest 
{ 
    public static void main(String[] args) { 
     TreeMap<Integer,Set<Integer>> index = new TreeMap<>(); 
     TreeMap<Set<Integer>,Integer> size = new TreeMap<>(comparing(Set::size)); 

     for(int i = 0; i < 5; i++) { 
     Set<Integer> set = new HashSet<>(); 
     for(int val = 0; val <= i; val++) { 
      set.add(val); 
     } 
     index.put(i, set); 
     size.put(set, i); 
     } 
     System.out.println(size.lastEntry()); // largest set size 
     System.out.println(index.get(2)); // random index 
    } 
} 

Answer 2

Как насчет этого?

public class MapAndPriority { 
    Map<Integer, Set<Integer>> sets = new HashMap<Integer, Set<Integer>>(); 
    PriorityQueue<Set<Integer>> byLength = new PriorityQueue<Set<Integer>>(1, new Comparator<Set<Integer>>() { 
     @Override 
     public int compare(Set<Integer> o1, Set<Integer> o2) { 
      // Compare in the reverse order! 
      return o2.size() - o1.size(); 
     } 
    }); 

    public void add(int i, Set<Integer> set) { 
     sets.put(i, set); 
     byLength.offer(set); // or Add, depending on the behavior you want 
    } 

    public Set<Integer> get(int i) { 
     return sets.get(i); 
    } 

    public Set<Integer> mostNodes() { 
     return byLength.peek(); 
    } 

    public void remove(int i) { 
     // sets.remove will return the removed set, so that will be removed from byLength. 
     // Need to handle case when i does not exist as a key in sets 
     byLength.remove(sets.remove(i)); 

    } 
} 

Если я понимаю, что вы хотите, то это будет:

1. Добавить новые наборы в о (NLog (п))
2. Regular карту get()
3. Получит самый большой набор (mostNodes()) in o (log (n))

То, что я сделал, это разместить все наборы в очереди приоритетов (вдоль карты) а затем предоставить приоритетную очередь компаратору, который сравнивается на основе размеров, так что меньший размер «больше». Таким образом, когда вы вызываете peek(), он вернет «минимальное» значение в очереди приоритетов, которое из-за нашего компаратора будет самым длинным. Я не занимался всевозможными краевыми случаями (например, удалять, когда пустым).

Вы можете ознакомиться с documentation для получения более подробной информации и о сложности.