Алгоритм пирамидальной сортировки (с кодом в Python и C++)
Что такое алгоритм пирамидальной сортировки?
Heap Sort — один из популярных и быстрых алгоритмов сортировки. Он построен на полной структуре данных двоичного дерева. Мы найдем максимальный элемент и поместим его на вершину максимальной кучи. Мы поместим его в родительский узел бинарного дерева.
Допустим, дан массив, данные = [10,5, 7, 9, 4, 11, 45, 17, 60].
В массиве, если i-й (i=0,1,2,3…) индекс является родительским узлом, то (2i+1) и (2i+2) будут левым и правым дочерними узлами. Создание полного двоичного дерева с помощью этого массива будет выглядеть так:
Мы выполним процесс heapify от начала до конца массива. Первоначально, если мы преобразуем массив в дерево, он будет выглядеть так, как показано выше. Мы видим, что он не поддерживает никаких свойств кучи (минимальная или максимальная куча). Мы получим отсортированный массив, выполнив процесс кучи для всех узлов.
Применение пирамидальной сортировки
Вот некоторые примеры использования алгоритма сортировки кучи:
- Для построения «приоритетных очередей» требуется пирамидальная сортировка. Потому что пирамидальная сортировка сохраняет сортировку элемента после каждой вставки.
- Структура данных кучи эффективна при поиске kth наибольший элемент в заданном массиве.
- Ядро Linux использует сортировку кучи по умолчанию. алгоритм сортировки так как имеет пространственную сложность O(1).
Создайте пирамидальную сортировку с примером
Здесь мы построим максимальную кучу из следующего полного двоичного дерева.
Листовыми узлами являются 17, 60, 4, 11 и 45. У них нет дочерних узлов. Вот почему они являются листовыми узлами. Итак, мы запустим метод heapify из родительского узла. Вот шаги:
Шаг 1) Выберите самое левое поддерево. Если дочерние узлы больше, поменяйте местами родительский узел с дочерним узлом.
Здесь родительским узлом является 9. А дочерними узлами являются 17 и 60. Поскольку 60 является самым большим, 60 и 9 будут заменены местами для сохранения максимальная куча.
Шаг 2) Теперь самое левое поддерево разбито на кучу. Следующий родительский узел — 7. У этого родителя есть два дочерних узла, самый большой — 45. Таким образом, 45 и 7 будут заменены местами.
Шаг 3) Узлы 60 и 4 имеют родительский узел 5. Поскольку «5» меньше дочернего узла 60, он будет заменен.
Шаг 4) Теперь у узла 5 есть дочерний узел 17,9. Это не поддерживает свойство максимальной кучи. Итак, 5 будет заменено на 17.
Шаг 5) Узел 10 будет заменен на 60, затем заменен на 17. Процесс будет выглядеть следующим образом.
Шаг 6) До шага 5 мы создали максимальную кучу. Каждый родительский узел больше своих дочерних узлов. Корневой узел имеет максимальное значение (60).
Примечание: Чтобы создать отсортированный массив, нам нужно заменить узел с максимальным значением его преемником.
Этот процесс называется «извлечь максимум». Поскольку 60 — это максимальный узел, мы зафиксируем его позицию на нулевом индексе и создадим кучу без узла 0.
Шаг 7) Поскольку 60 удалено, следующим максимальным значением будет 45. Мы снова выполним процесс «Извлечение максимума» из узла 45.
На этот раз мы получим 45 и заменим корневой узел его преемником 17.
Нам нужно выступить»Извлечь Макса», пока все элементы не будут отсортированы.
После выполнения этих шагов, пока мы не извлечем все максимальные значения, мы получим следующий массив.
Что такое двоичная куча?
Двоичная куча — это своего рода полная бинарное дерево структура данных. В такой древовидной структуре родительский узел либо больше, либо меньше дочерних узлов. Если родительский узел меньше, то куча называется «Минимальной кучей», а если родительский узел больше, куча называется «Максимальной кучей».
Вот примеры минимальной кучи и максимальной кучи.
Если на приведенном выше рисунке вы заметили «Минимальную кучу», родительский узел всегда меньше своих дочерних узлов. В голове дерева мы можем найти наименьшее значение 10.
Аналогично, для «Максимальной кучи» родительский узел всегда больше дочерних узлов. Максимальный элемент присутствует в головном узле для «Максимальной кучи».
Что такое «Heapify»?
«Heapify» — это принцип кучи, который обеспечивает положение узла. В Heapify максимальная куча всегда поддерживает связь с родительским и дочерним узлами, и родительский узел будет больше, чем дочерние узлы.
Например, если добавляется новый узел, нам нужно изменить форму кучи. Однако нам может потребоваться изменить или поменять местами узлы или переупорядочить массив. Этот процесс изменения формы кучи называется «кучей».
Вот пример того, как работает heapify:
Вот шаги для heapify:
Шаг 1) Добавлен узел 65 как правый дочерний элемент узла 60.
Шаг 2) Проверьте, больше ли вновь добавленный узел родительского.
Шаг 3) Поскольку он больше родительского узла, мы поменяли местами правый дочерний узел с его родителем.
Как построить кучу
Прежде чем создавать кучу или собирать дерево в кучу, нам нужно знать, как мы будем ее хранить. Поскольку куча представляет собой полное двоичное дерево, лучше использовать массив для хранения данных кучи.
Допустим, массив содержит всего n элементов. Если «i»-й индекс является родительским узлом, то левый узел будет находиться по индексу (2и+1), и правый узел будет по индексу (2и+2). Мы предполагаем, что индекс массива начинается с 0.
Используя это, давайте сохраним максимальную кучу в виде массива:
Алгоритм heapify поддерживает свойство кучи. Если родительский узел не имеет крайнего значения (меньше или больше), он будет заменен самым крайним дочерним узлом.
Вот шаги для создания максимальной кучи:
Шаг 1) Начните с листового узла.
Шаг 2) Найдите максимум между родителем и детьми.
Шаг 3) Поменяйте местами узлы, если дочерний узел имеет большее значение, чем родительский.
Шаг 4) Поднимитесь на один уровень выше.
Шаг 5) Выполните шаги 2,3,4, пока не достигнем индекса 0 или не отсортируем все дерево.
Вот псевдокод для рекурсивной кучи (максимальная куча):
def heapify(): input→ array, size, i largest = i left = 2*i + 1 right = 2*i + 2 if left<n and array[largest ] < array[left]: largest = left if right<n and array[largest ] < array[right]: largest = right If largest not equals i: swap(array[i],array[largest]) heapify(array,n,largest)
Псевдокод для пирамидальной сортировки
Вот псевдокод алгоритма сортировки кучей:
Heapify(numbers as an array, n as integer, i as integer): largest = i left = 2i+1 right= 2i+2 if(left<=n) and (numbers[i]<numbers[left]) largest=left if(right<=n) and (numbers[i]<numbers[right]) largest=right if(largest != i) swap(numbers[i], numbers[largest]) Heapify(numbers,n,largest) HeapSort(numbers as an array): n= numbers.size() for i in range n/2 to 1 Heapify(numbers,n,i) for i in range n to 2 Swap numbers[i] with numbers[1] Heapify(numbers,i,0)
Пример кода сортировки кучи в C++
#include <iostream> using namespace std; void display(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << "\t"; } cout << endl; } void heapify(int numbers[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && numbers[left] < numbers[largest]) { largest = left; } if (right < n && numbers[right] < numbers[largest]) { largest = right; } if (largest != i) { //uncomment the following line to see details in output //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl; swap(numbers[i], numbers[largest]); heapify(numbers, n, largest); } } void heapSort(int numbers[], int n) { for (int i = n/2 - 1; i >= 0; i--) { heapify(numbers, n, i); //uncomment the following line to see details in output //cout<<"Heapify:\t"; //display(numbers,n); } for (int i = n - 1; i >= 0; i--) { swap(numbers[0], numbers[i]); heapify(numbers, i, 0); } } int main() { int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60}; int size = sizeof(numbers) / sizeof(numbers[0]); cout<<"Initial Array:\t"; display(numbers,size); heapSort(numbers, size); cout<<"Sorted Array (descending order):\t"; display(numbers, size); }
Вывод:
Initial Array: 10 5 7 9 4 11 45 17 60 Sorted Array (descending order): 60 45 17 11 10 9 7 5 4
Пример кода сортировки кучи в Python
def display(arr): for i in range(len(arr)): print(arr[i], end = "\t") print() def heapify(numbers, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and numbers[left] < numbers[largest]: largest = left if right < n and numbers[right] < numbers[largest]: largest = right if largest != i: numbers[i], numbers[largest] = numbers[largest], numbers[i] heapify(numbers, n, largest) def heapSort(items, n): for i in range(n //2,-1,-1): heapify(items, n, i) for i in range(n - 1, -1, -1): items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)
Вывод:
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
Анализ временной и пространственной сложности пирамидальной сортировки
Есть временная сложность и пространственная сложность, которые мы можем проанализировать для сортировки кучи. Для временной сложности мы имеем следующие случаи:
- лучший случай
- Средний случай
- Худший случай
Куча реализована в виде полного двоичного дерева. Итак, на нижнем уровне бинарного дерева будет максимальное количество узлов. Если нижний уровень имеет n узлов, то верхний уровень будет иметь n/2 узлов.
В этом примере уровень 3 содержит четыре элемента, уровень 2 — два элемента, а уровень 1 — один элемент. Если всего элементов n, высота или общий уровень будет равна Журнал2(П). Таким образом, вставка одного элемента может занять максимум итераций Log(n).
Когда мы хотим взять максимальное значение из кучи, мы просто берем корневой узел. Затем снова запустите heapify. Каждая куча занимает Журнал2(П) время. Извлечение максимума занимает время O(1).
лучший Case Time Complexity для алгоритма Heap Sort
Когда все элементы массива уже отсортированы, для построения кучи потребуется время O(n). Потому что, если список отсортирован, вставка элемента займет постоянное время, равное O (1).
Таким образом, для создания максимальной или минимальной кучи в лучшем случае потребуется время O(n).
Средняя сложность случая для алгоритма пирамидальной сортировки
Вставка элемента или извлечение максимального значения требует времени O(log(n)) . Таким образом, средняя временная сложность алгоритма сортировки кучи равна О(п лог(п)).
Наихудшая временная сложность алгоритма пирамидальной сортировки
Как и в среднем случае, в худшем случае мы можем выполнить heapify n раз. Каждая heapify будет стоить O(log(n)) времени. Таким образом, наихудшая временная сложность будет равна О(п лог(п)).
Пространственная сложность алгоритма пирамидальной сортировки
Сортировка кучей — это алгоритм, разработанный на месте. Это означает, что для выполнения задачи не требуется никакой дополнительной или временной памяти. Если мы увидим реализацию, то заметим, что мы использовали swap() для выполнения обмена узлами. Никакого другого списка или массива не требовалось. Итак, пространственная сложность равна O(1).