Может ли TreeMap сортировать по убыванию?

TreeMap: сортировка по убыванию

Краткий ответ: Да, TreeMap полностью поддерживает сортировку по убыванию через использование Comparator. Давайте разберем несколько способов это сделать.

1. Использование Comparator.reverseOrder()

Это самый простой и рекомендуемый способ:

import java.util.*;

public class TreeMapReverseExample {
    public static void main(String[] args) {
        // TreeMap с сортировкой по убыванию
        TreeMap<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());
        
        map.put("apple", 3);
        map.put("banana", 1);
        map.put("cherry", 2);
        map.put("date", 4);
        
        System.out.println(map);
        // Результат: {date=4, cherry=2, banana=1, apple=3}
        // Ключи отсортированы: date > cherry > banana > apple
    }
}

2. Кастомный Comparator

Для сортировки объектов с нестандартным порядком:

public class Person {
    private String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class CustomComparatorExample {
    public static void main(String[] args) {
        // TreeMap, сортирующая по возрасту в убывающем порядке
        TreeMap<Person, String> map = new TreeMap<>((p1, p2) -> {
            // Сортировка по возрасту: вычитаем в обратном порядке
            return Integer.compare(p2.age, p1.age);
        });
        
        map.put(new Person("Alice", 30), "Engineer");
        map.put(new Person("Bob", 25), "Designer");
        map.put(new Person("Charlie", 35), "Manager");
        
        map.forEach((person, role) -> 
            System.out.println(person + " -> " + role)
        );
        // Результат:
        // Charlie (35) -> Manager
        // Alice (30) -> Engineer
        // Bob (25) -> Designer
    }
}

3. Сравнение: TreeMap vs HashMap

public class ComparisonExample {
    public static void main(String[] args) {
        // HashMap: БЕЗ сортировки
        Map<Integer, String> hashMap = new HashMap<>();
        hashMap.put(5, "Five");
        hashMap.put(1, "One");
        hashMap.put(3, "Three");
        hashMap.put(2, "Two");
        hashMap.put(4, "Four");
        
        System.out.println("HashMap: " + hashMap);
        // Результат: {1=One, 5=Five, 3=Three, 2=Two, 4=Four} (случайный порядок)
        
        // TreeMap: сортировка по возрастанию (по умолчанию)
        Map<Integer, String> treeMapAsc = new TreeMap<>(hashMap);
        System.out.println("TreeMap (ascending): " + treeMapAsc);
        // Результат: {1=One, 2=Two, 3=Three, 4=Four, 5=Five}
        
        // TreeMap: сортировка по убыванию
        Map<Integer, String> treeMapDesc = new TreeMap<>(Comparator.reverseOrder());
        treeMapDesc.putAll(hashMap);
        System.out.println("TreeMap (descending): " + treeMapDesc);
        // Результат: {5=Five, 4=Four, 3=Three, 2=Two, 1=One}
    }
}

4. Производительность операций

public class PerformanceExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> descendingMap = new TreeMap<>(Comparator.reverseOrder());
        
        // Вставка: O(log n)
        for (int i = 0; i < 1000; i++) {
            descendingMap.put(i, "Value" + i);
        }
        
        // Поиск: O(log n)
        long start = System.nanoTime();
        String value = descendingMap.get(500);
        long searchTime = System.nanoTime() - start;
        
        // Получение ключей в порядке убывания: O(n)
        for (Integer key : descendingMap.keySet()) {
            // Ключи уже отсортированы в порядке убывания
        }
        
        // Получение последнего элемента (максимума): O(1)
        Integer lastKey = descendingMap.lastKey();
        
        // Получение первого элемента (минимума): O(1)
        Integer firstKey = descendingMap.firstKey();
    }
}

5. Использование tailMap() и headMap() с убыванием

public class RangeExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder());
        
        for (int i = 1; i <= 10; i++) {
            map.put(i, "Value" + i);
        }
        // map: {10=Value10, 9=Value9, ..., 1=Value1}
        
        // Получить элементы от 8 до 3 (в порядке убывания)
        Map<Integer, String> subMap = map.subMap(8, true, 3, true);
        System.out.println("SubMap [8, 3]: " + subMap);
        // {8=Value8, 7=Value7, 6=Value6, 5=Value5, 4=Value4, 3=Value3}
        
        // Получить элементы >= 7 (в порядке убывания)
        Map<Integer, String> headMap = map.headMap(7, true);
        System.out.println("HeadMap [7, ...]: " + headMap);
        // {10=Value10, 9=Value9, 8=Value8, 7=Value7}
        
        // Получить элементы < 4 (в порядке убывания)
        Map<Integer, String> tailMap = map.tailMap(4, false);
        System.out.println("TailMap [..., 4): " + tailMap);
        // {3=Value3, 2=Value2, 1=Value1}
    }
}

6. Сравнение Comparator подходов

public class ComparatorComparison {
    public static void main(String[] args) {
        // Способ 1: reverseOrder() — РЕКОМЕНДУЕТСЯ
        TreeMap<Integer, String> map1 = new TreeMap<>(Comparator.reverseOrder());
        
        // Способ 2: Lambda expression
        TreeMap<Integer, String> map2 = new TreeMap<>((a, b) -> b.compareTo(a));
        
        // Способ 3: Collections.reverseOrder() — старый стиль
        TreeMap<Integer, String> map3 = new TreeMap<>(Collections.reverseOrder());
        
        // Все три способа эквивалентны
        // Prefer #1 (Comparator.reverseOrder()) — более читаемо
    }
}

7. Практический пример: ранжирование по результатам

public class Contestant {
    private String name;
    private int score;
    
    public Contestant(String name, int score) {
        this.name = name;
        this.score = score;
    }
    
    @Override
    public String toString() {
        return name + " (" + score + " points)";
    }
    
    public int getScore() {
        return score;
    }
}

public class LeaderboardExample {
    public static void main(String[] args) {
        // Таблица лидеров: сортировка по результатам в убывающем порядке
        TreeMap<Integer, List<Contestant>> leaderboard = 
            new TreeMap<>((s1, s2) -> Integer.compare(s2, s1));  // Убывание
        
        // Добавляем результаты
        Contestant[] contestants = {
            new Contestant("Alice", 100),
            new Contestant("Bob", 85),
            new Contestant("Charlie", 100),
            new Contestant("David", 70)
        };
        
        for (Contestant c : contestants) {
            leaderboard.computeIfAbsent(c.getScore(), k -> new ArrayList<>())
                       .add(c);
        }
        
        // Вывод в порядке убывания результатов
        System.out.println("Leaderboard (descending):");
        leaderboard.forEach((score, contestants_list) -> {
            System.out.println(score + " points:");
            contestants_list.forEach(c -> System.out.println("  - " + c));
        });
        
        // Результат:
        // Leaderboard (descending):
        // 100 points:
        //   - Alice (100 points)
        //   - Charlie (100 points)
        // 85 points:
        //   - Bob (85 points)
        // 70 points:
        //   - David (70 points)
    }
}

Выводы

Да, TreeMap может сортировать по убыванию:

✓ Используй: new TreeMap<>(Comparator.reverseOrder())

✓ Преимущества TreeMap:

• Автоматическая сортировка при вставке
• O(log n) для вставки, удаления, поиска
• Возможность получения диапазонов элементов
• Итерация в отсортированном порядке

✗ Недостатки:

• Медленнее HashMap в некоторых случаях
• Требует определения Comparator
• Ключи должны быть сравнимы

Когда использовать:

• Когда нужны данные всегда отсортированными
• Для лидербордов, рейтингов
• Когда нужны range queries (subMap, headMap, tailMap)
• Когда нужны минимум/максимум в O(1)