Двоичная куча, HeapSort
Определения
Двоичная куча — это полное бинарное дерево, которое удовлетворяет свойству кучи. В таком дереве все уровни, кроме последнего, полностью заполнены, а узлы последнего уровня располагаются слева направо без пропусков.
- Полнота: Все уровни, кроме, возможно, последнего, полностью заполнены, а узлы последнего уровня располагаются слева направо.
- Свойство кучи: Для максимальной кучи каждый узел больше или равен своим потомкам; для минимальной кучи каждый узел меньше или равен своим потомкам.
HeapSort — это эффективный алгоритм сортировки, основанный на сравнении, который использует структуру данных двоичной кучи.
- Построение максимальной кучи: Преобразуйте неотсортированный массив в максимальную кучу, где каждый узел больше или равен своим потомкам.
- Извлечение элементов из кучи: Последовательно удаляйте наибольший элемент из кучи (корень кучи) и перемещайте его в конец массива. Каждый раз уменьшайте размер кучи на один.
- Восстановление кучи: После удаления корня перемещайте последний элемент кучи на его место и восстанавливайте структуру кучи.
