Алгоритм сортировки на месте с N log N в худшем случае.

Используя Max-Heap, мы можем сортировать элементы данных.

  • Мы можем создать max-heap со всеми N ключами.
  • Неоднократно удаляем максимальный ключ.

Строительство кучи: Создайте максимальную кучу, используя восходящий метод.

Сортировка кучи:

  • Удалите максимум, по одному.
  • Оставить в массиве вместо обнуления.

Нижняя линия.

Heapsort оптимален как по времени, так и по пространству, но:

  • Внутренний цикл длиннее, чем у быстрой сортировки.
  • Плохо использует кэш-память.
  • Нестабильный