Алгоритм сортировки на месте с N log N в худшем случае.
Используя Max-Heap, мы можем сортировать элементы данных.
- Мы можем создать max-heap со всеми N ключами.
- Неоднократно удаляем максимальный ключ.
Строительство кучи: Создайте максимальную кучу, используя восходящий метод.
Сортировка кучи:
- Удалите максимум, по одному.
- Оставить в массиве вместо обнуления.
Нижняя линия.
Heapsort оптимален как по времени, так и по пространству, но:
- Внутренний цикл длиннее, чем у быстрой сортировки.
- Плохо использует кэш-память.
- Нестабильный