Раскройте возможности пирамидальной сортировки в Python с помощью нашего подробного руководства. Погрузитесь глубже в его алгоритм, разберитесь с двоичными кучами и познакомьтесь с нашими примерами кода Python. Оптимизируйте свои навыки кодирования и знания структур данных уже сегодня.
1. Введение в пирамидальную сортировку
Heap Sort — это алгоритм сортировки на основе сравнения, который использует свойства двоичной кучи. Он делит входные данные на отсортированную и несортированную область и итеративно сжимает несортированную область, извлекая самый большой элемент и перемещая его в отсортированную область. Магия пирамидальной сортировки заключается в ее способности сортировать на месте, а это означает, что для ее работы требуется только постоянный объем дополнительной памяти.
2. Понимание кучи
Прежде чем углубиться в сам алгоритм, важно понять концепцию двоичной кучи.
2.1. Что такое куча?
Куча — это полное двоичное дерево, которое удовлетворяет любому из двух свойств:
- Максимальная куча: каждый родительский узел больше или равен своим дочерним узлам.
- Минимальная куча. Каждый родительский узел меньше или равен своим дочерним узлам.
В контексте пирамидальной сортировки обычно используется Max-Heap.
3. Алгоритм пирамидальной сортировки
Алгоритм пирамидальной сортировки можно разбить на следующие этапы:
- Создайте Max-Heap из входных данных.
- Самый большой элемент хранится в корне кучи. Замените его последним элементом кучи, уменьшив размер кучи на единицу. Затем сложите корень дерева в кучу.
- Повторите шаг 2, пока размер кучи больше 1.
4. Реализация Python
Переведем алгоритм в код Python:
def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build a maxheap for i in range(n…