Алгоритм сортировки кучей (с Code in Python и C++)
Сара Чен
⚡ Умное резюме
Алгоритм сортировки кучей сортирует массив, создавая бинарную кучу и многократно извлекая её содержимое.tracпомещая его корневое значение в отсортированную секцию. Этот ресурс объясняет алгоритм heapify, максимальную и минимальную кучи, псевдокод и полный код. Python и C++ Реализации с анализом временной сложности.
Что такое алгоритм пирамидальной сортировки?
Сортировка кучей — один из популярных и быстрых алгоритмов сортировки. Он основан на структуре данных полного бинарного дерева. Для максимальной кучи мы будем искать максимальный элемент и помещать его на вершину. Мы поместим его на родительский узел бинарного дерева.
Допустим, дан массив, данные = [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).
Примечание: Чтобы создать отсортированный массив, нам нужно заменить узел с максимальным значением его преемником.
Этот процесс называется «extracт макс». Поскольку 60 — это максимальный узел, мы зафиксируем его позицию на нулевом индексе и создадим кучу без узла 0.
Шаг 7) Поскольку 60 удаляется, следующее максимальное значение равно 45. Мы выполним процесс «Ex».trac"t Max" снова с узла 45.
На этот раз мы получим 45 и заменим корневой узел его преемником 17.
Нам нужно выступить»Extracт Макс.», пока все элементы не будут отсортированы.
После выполнения этих шагов до тех пор, пока мы не выполнимtracПринимая все максимальные значения, мы получим следующий массив.
Что такое двоичная куча?
Двоичная куча — это своего рода полная бинарное дерево структура данных. В такой древовидной структуре родительский узел либо больше, либо меньше дочерних узлов. Если родительский узел меньше, то куча называется «Минимальной кучей», а если родительский узел больше, куча называется «Максимальной кучей».
Вот примеры минимальной кучи и максимальной кучи.
Если на приведенном выше рисунке вы заметили «Минимальную кучу», родительский узел всегда меньше своих дочерних узлов. В голове дерева мы можем найти наименьшее значение 10.
Аналогично, для «Максимальной кучи» родительский узел всегда больше дочерних узлов. Максимальный элемент присутствует в головном узле для «Максимальной кучи».
Что такое «Heapify»?
«Heapify» — это принцип кучи, который обеспечивает положение узла. В Heapify максимальная куча всегда поддерживает связь с родительским и дочерним узлами, и родительский узел будет больше, чем дочерние узлы.
Например, если добавляется новый узел, нам нужно изменить форму кучи. Однако нам также может потребоваться изменить или поменять местами узлы или перестроить массив. Этот процесс изменения формы кучиping Куча называется "кучеобразующей".
Вот пример того, как работает 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)
Прозвище Code для сортировки кучей
Вот псевдокод алгоритма сортировки кучей:
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)
Пример сортировки кучей Code in 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
Пример сортировки кучей Code in 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(П) время. БывшийtracНахождение максимума занимает время O(1).
лучший Case Time Complexity для алгоритма Heap Sort
Когда все элементы массива уже отсортированы, для построения кучи потребуется время O(n). Потому что, если список отсортирован, вставка элемента займет постоянное время, равное O (1).
Таким образом, для создания максимальной или минимальной кучи в лучшем случае потребуется время O(n).
Средняя сложность случая для алгоритма пирамидальной сортировки
Вставка элемента или экспонатаtracДостижение максимального значения занимает время O(log(n)). Таким образом, средняя временная сложность алгоритма сортировки кучей составляет О(п лог(п)).
Наихудшая временная сложность алгоритма пирамидальной сортировки
Как и в среднем случае, в худшем случае мы можем выполнить heapify n раз. Каждая heapify будет стоить O(log(n)) времени. Таким образом, наихудшая временная сложность будет равна О(п лог(п)).
Пространственная сложность алгоритма пирамидальной сортировки
Сортировка кучей — это алгоритм, разработанный на месте. Это означает, что для выполнения задачи не требуется никакой дополнительной или временной памяти. Если мы увидим реализацию, то заметим, что мы использовали swap() для выполнения обмена узлами. Никакого другого списка или массива не требовалось. Итак, пространственная сложность равна O(1).
