Сортировка кучей (HeapSort): баланс памяти и производительности

Куча (heap) — двоичное дерево, удовлетворяющее свойству кучи: родитель всегда больше (max-heap) или меньше (min-heap) своих потомков.

public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        
        // Построение max-heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // Извлечение элементов из кучи
        for (int i = n - 1; i > 0; i--) {
            // Перемещаем корень (максимум) в конец
            swap(arr, 0, i);
            
            // Восстанавливаем кучу для уменьшенного массива
            heapify(arr, i, 0);
        }
    }
    
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;        // Инициализируем корень как наибольший
        int left = 2 * i + 1;   // Левый потомок
        int right = 2 * i + 2;  // Правый потомок
        
        // Если левый потомок больше корня
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // Если правый потомок больше текущего наибольшего
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // Если наибольший не корень
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest); // Рекурсивно heapify затронутое поддерево
        }
    }
}

Особенности HeapSort

Неустойчивость: Перестановки элементов нарушают исходный порядок
Дополнительная память O(1): Работает на месте (in-place)
Гарантированная сложность O(n log n): Худший случай не хуже
Кэш-недружественность: Случайный доступ к элементам при heapify

Применение в гибридных алгоритмах

HeapSort используется как защитный механизм:
Introsort: Быстрая сортировка + HeapSort при глубокой рекурсии
Heapsort для малых n: В некоторых реализациях для небольших массивов
Реализация приоритетных очередей: Структура кучи — основа PriorityQueue

Сравнительный анализ: три подхода к эффективности

По устойчивости
Устойчивые: MergeSort (сохраняет порядок равных)
Неустойчивые: QuickSort, HeapSort (меняют порядок)

По использованию памяти
O(1) дополнительной памяти: HeapSort (in-place)
O(log n) стековой памяти: QuickSort (рекурсия)
O(n) дополнительной памяти: MergeSort (временный массив)

По гарантиям времени
Всегда O(n log n): MergeSort, HeapSort
O(n²) в худшем, O(n log n) в среднем: QuickSort

По практической производительности
QuickSort: Самый быстрый в среднем случае, лучшая локальность кэша
HeapSort: Гарантии без доп. памяти, но медленнее из-за плохой локальности
MergeSort: Стабильность и параллелизуемость, но требует памяти


Применение парадигмы «Разделяй и властвуй»

Оба основных алгоритма следуют парадигме:

QuickSort:
Разделение: Partition по pivot (O(n))
Покорение: Рекурсивная сортировка двух частей
Объединение: Уже отсортировано на месте

MergeSort:
Разделение: Пополам (O(1))
Покорение: Рекурсивная сортировка половин
Объединение: Merge двух отсортированных массивов (O(n))

Анализ сложности

Рекуррентное соотношение для обоих алгоритмов (в среднем для QuickSort):
T(n) = 2T(n/2) + O(n)
По основной теореме о рекуррентных соотношениях это дает O(n log n).

Почему это эффективно
Разделение задачи размером n на две подзадачи размером n/2 уменьшает общий объем работы. Если бы разделение было линейным (например, на задачи размером n-1 и 1), сложность оставалась бы квадратичной.


#Java #для_новичков #beginner #algorithm #sorted #HeapSort

Раздел 7. Алгоритмы

Глава 3. Алгоритмы сортировки и подготовка данных

Практика : Реализовать сортировку выбором и сортировку слиянием для книг по году издания. Убедиться, что слияние сохраняет относительный порядок (устойчивость). Использовать Collections.sort() и исследовать, какой алгоритм применяется (Timsort — гибрид вставок и слияния).

Анализ: В каком случае для библиотечного приложения важна устойчивость сортировки? Когда можно пожертвовать памятью (MergeSort) ради гарантии, а когда важна экономия памяти (HeapSort)?

Мы реализуем две классические сортировки вручную:
Сортировка выбором (Selection Sort) — простой, понятный, но неэффективный алгоритм O(n²)
Сортировка слиянием (Merge Sort) — устойчивый алгоритм с гарантированной сложностью O(n log n) и дополнительной памятью O(n)


Подготовка к уроку

Перед началом убедитесь, что в проекте есть:
Класс Book с полями title, author, year (все поля должны иметь геттеры)
Класс Library с полем List<Book> books = new ArrayList<>()
Метод printAllBooks() или аналогичный для вывода списка книг с номерами

Рекомендуемые импорты в Library.java:
Javaimport java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;


Шаг 1. Подготовка тестовых данных

Перед реализацией алгоритмов добавьте в main или в метод инициализации библиотеки набор книг с намеренными дубликатами годов и авторов, чтобы можно было проверить устойчивость сортировки.
Пример набора данных, который вы должны создать самостоятельно:

"1984", "Оруэлл", 1949
"Скотный двор", "Оруэлл", 1945
"Война и мир", "Толстой", 1869
"Анна Каренина", "Толстой", 1877
"Мастер и Маргарита", "Булгаков", 1967
"Собачье сердце", "Булгаков", 1925
"Преступление и наказание", "Достоевский", 1866
"Идиот", "Достоевский", 1869
"Братья Карамазовы", "Достоевский", 1880

Обратите внимание: два автора имеют одинаковый год (Оруэлл не имеет дублей, Достоевский имеет два произведения в 1869 году).


Шаг 2. Реализация сортировки выбором (Selection Sort) по году

Создайте в классе Library метод:public void selectionSortByYear()

Внутри метода:
Переберите массив/список внешним циклом от 0 до books.size()–2
Для каждого i найдите индекс минимального года в подмассиве [i … end]
Если найденный минимум не равен i — поменяйте местами элементы i и minIndex
После окончания внешнего цикла список должен быть отсортирован по году

После сортировки вызовите printAllBooks() — чтобы увидеть результат

Важные моменты для самостоятельной реализации:
Работайте с индексами (не создавайте новый список)
Сравнивайте book.getYear()
Обменяйте объекты целиком (не отдельные поля)


#Java #для_новичков #beginner #algorithm #sorted #HeapSort #Практика

Шаг 3. Реализация сортировки слиянием (Merge Sort) по году

Создайте метод: public void mergeSortByYear()

Реализуйте классический рекурсивный Merge Sort:
Создайте вспомогательный метод mergeSort(List<Book> list, int left, int right)

Если left < right:
mid = (left + right) / 2
Рекурсивно сортируйте левую половину
Рекурсивно сортируйте правую половину
Слейте две отсортированные половины в методе merge()

Реализуйте метод merge(List<Book> list, int left, int mid, int right):
Создайте временный список temp нужного размера
Два указателя i = left, j = mid+1
Пока обе половины не закончились — сравнивайте и копируйте меньший элемент
Докопируйте остаток левой или правой половины
Скопируйте temp обратно в исходный список на позиции left..right

Ключевой момент устойчивости:
Merge Sort устойчив — при равных ключах сохраняется относительный порядок исходных элементов.
После сортировки вызовите printAllBooks() и убедитесь, что книги Достоевского 1869 года остались в исходном порядке (Преступление → Идиот).
Шаг 4. Использование встроенной сортировки (Collections.sort и List.sort)

Создайте метод sortWithCollections():
Вызовите Collections.sort(books) — поскольку Book реализует Comparable по названию (из предыдущего урока), отсортирует по названию
Затем вызовите books.sort(Comparator.comparingInt(Book::getYear)) — сортировка по году
Затем вызовите books.sort(Comparator.comparing(Book::getAuthor).thenComparingInt(Book::getYear)) — по автору, затем по году

После каждой сортировки выводите список и наблюдайте порядок.

Исследование Timsort:

Начиная с Java 7, Collections.sort() и List.sort() используют Timsort — гибридный алгоритм:
Сортировка вставками для малых подмассивов (run ≤ 32)
Слияние (merge) для больших
Очень эффективен на реальных данных (частично отсортированных)
Устойчив — сохраняет относительный порядок равных элементов

Анализ: Когда важна устойчивость сортировки?

Устойчивость (stable sort) — когда при равных ключах сохраняется исходный относительный порядок элементов.

В библиотечном приложении устойчивость важна в следующих случаях:
Сортировка по году, но хочется сохранить алфавитный порядок авторов при одинаковом годе
→ Если два произведения Достоевского вышли в 1869 году — после сортировки по году они должны остаться в порядке появления в каталоге или по алфавиту названий.
Сортировка по рейтингу, но при равном рейтинге важен порядок добавления
→ Пользователь добавил книги в определённом порядке — при равном рейтинге хочется видеть их в этом же порядке.
Многоуровневая сортировка
→ Сначала по автору, затем по году — устойчивость гарантирует, что внутри одного автора книги останутся в порядке добавления или по названию.

Когда устойчивость не критична:
Сортировка по уникальному полю (ISBN, ID) — равных элементов нет
Когда порядок внутри группы не имеет значения (например, только по жанру)
Когда важна максимальная скорость и экономия памяти, а не порядок

Сравнение по памяти и устойчивости:

Прогноз при росте данных:
100 книг → любой алгоритм за миллисекунды
100 000 книг → Selection Sort — секунды, остальные — десятки миллисекунд
1 000 000 книг → Selection Sort — часы, Timsort/Merge — секунды, HeapSort — чуть быстрее MergeSort за счёт меньшей памяти

Вывод для библиотеки:
Основной выбор — List.sort() (Timsort): устойчивый, быстрый, адаптивный
Merge Sort вручную — только если нужно изучить алгоритм или требуется явный контроль
HeapSort — если память критична (очень редкий случай)
Selection Sort — исключительно для обучения


Практическое задание (объёмное)

Реализуйте selectionSortByYear() вручную.
Реализуйте рекурсивный mergeSortByYear() с вспомогательным merge.

Добавьте методы:
sortByTitleUsingCollections()
sortByAuthorThenYearUsingComparator()
sortByYearUsingLambda()

В main добавьте 10+ книг с дубликатами годов и авторов.
Выполните все сортировки подряд и выводите список после каждой.
Сравните порядок книг Достоевского 1869 года до и после сортировки по году — убедитесь в устойчивости Timsort и MergeSort.

#Java #для_новичков #beginner #algorithm #sorted #HeapSort #Практика