Временная сложность
Лучший: O(n log n)
Средний: O(n log n)
Худший: O(n log n)
Пирамидальная сортировка использует структуру данных «двоичная куча» для упорядочивания элементов. Сначала из массива строится max-heap (максимальная куча), затем из неё последовательно извлекается максимальный элемент.
Как работает алгоритм:
1. Построить max-heap из входного массива
2. Самый большой элемент оказывается в корне (индекс 0)
3. Поменять его местами с последним элементом и уменьшить размер кучи
4. Выполнить heapify для корня, чтобы восстановить свойство max-heap
5. Повторять, пока куча не опустеет
Временная сложность:
Лучшая: O(n log n)
Средняя: O(n log n)
Худшая: O(n log n)
Пространственная сложность: O(1) — сортировка на месте
Свойства:
- Не является стабильной
- Выполняется на месте
- Гарантированная производительность O(n log n)
Пирамидальная сортировка сочетает преимущества сортировки слиянием (гарантированная сложность O(n log n)) и быстрой сортировки (выполнение на месте). Полезна, когда важна производительность в худшем случае.
Похожие алгоритмы
Частые вопросы
- Что такое Пирамидальная сортировка (Heap Sort)?
- Пирамидальная сортировка использует структуру данных «двоичная куча» для упорядочивания элементов. Сначала из массива строится max-heap (максимальная куча), затем из неё последовательно извлекается максимальный элемент.
- Какова сложность Пирамидальная сортировка (Heap Sort)?
- Время (среднее): O(n log n) · Память: O(1)
- Для кого предназначена визуализация Пирамидальная сортировка (Heap Sort)?
- Визуализация Пирамидальная сортировка (Heap Sort) рассчитана на средний уровень в категории «Сортировка». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Пирамидальная сортировка (Heap Sort)?
- В той же категории (Сортировка) вы можете изучить: Bubble Sort, Selection Sort, Insertion Sort. Каждый из них имеет интерактивную визуализацию.