В этом руководстве вы узнаете, как работает алгоритм сортировки кучи. Также вы найдете рабочие примеры сортировки кучи на C, C ++, Java и Python.
Heap Sort - популярный и эффективный алгоритм сортировки в компьютерном программировании. Чтобы научиться писать алгоритм сортировки кучи, необходимо знать два типа структур данных - массивы и деревья.
Первоначальный набор чисел, которые мы хотим отсортировать, хранится в массиве, например, (10, 3, 76, 34, 23, 32)и после сортировки мы получаем отсортированный массив(3,10,23,32,34,76)
Сортировка кучи работает путем визуализации элементов массива как особого вида полного двоичного дерева, называемого кучей.
В качестве предварительного условия вы должны знать полное двоичное дерево и структуру данных кучи.
Связь между индексами массивов и элементами дерева
Полное двоичное дерево обладает интересным свойством, которое мы можем использовать для поиска потомков и родителей любого узла.
Если индекс любого элемента в массиве равен i, элемент в индексе 2i+1станет левым дочерним элементом, а элемент в 2i+2индексе станет правым дочерним элементом . Кроме того, родительский элемент любого элемента с индексом i задается нижней границей (i-1)/2.
Связь между индексами массива и кучи
Давай проверим,
Левый дочерний элемент 1 (индекс 0) = элемент в (2 * 0 + 1) index = элемент в 1 index = 12 Правый дочерний элемент 1 = элемент в (2 * 0 + 2) index = элемент в 2 index = 9 Аналогично, Левый дочерний элемент 12 (индекс 1) = элемент в (2 * 1 + 1) index = элемент в 3 index = 5 Правый дочерний элемент 12 = элемент в (2 * 1 + 2) index = элемент в 4 index = 6
Также подтвердим, что правила поиска родителя любого узла выполняются.
Родитель 9 (позиция 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Родитель 12 (позиция 1) = (1-1) / 2 = 0 index = 1
Понимание этого сопоставления индексов массива с позициями в дереве имеет решающее значение для понимания того, как работает структура данных кучи и как она используется для реализации сортировки кучи.
Что такое структура данных кучи?
Куча - это особая древовидная структура данных. Считается, что двоичное дерево следует структуре данных кучи, если
- это полное двоичное дерево
- Все узлы в дереве следуют тому свойству, что они больше, чем их дочерние элементы, т. Е. Самый большой элемент находится в корне и оба его дочерних элемента, и меньше, чем корень, и так далее. Такая куча называется max-heap. Если вместо этого все узлы меньше, чем их дочерние элементы, это называется минимальной кучей.
На следующей диаграмме в качестве примера показаны Max-Heap и Min-Heap.
Максимальная и минимальная куча
Чтобы узнать больше об этом, посетите страницу «Структура данных кучи».
Как "насыпать" дерево
Начиная с полного двоичного дерева, мы можем изменить его, чтобы оно стало Max-Heap, запустив функцию heapify для всех нелистовых элементов кучи.
Поскольку heapify использует рекурсию, это может быть трудно понять. Итак, давайте сначала подумаем о том, как бы вы могли заполнить дерево всего тремя элементами.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify базовые случаи
В приведенном выше примере показаны два сценария - один, в котором корень является самым большим элементом, и нам не нужно ничего делать. И еще один, в котором у корня был более крупный дочерний элемент, и нам нужно было поменять местами, чтобы сохранить свойство max-heap.
Если вы раньше работали с рекурсивными алгоритмами, вы, вероятно, определили, что это должен быть базовый случай.
Теперь давайте подумаем о другом сценарии, в котором существует более одного уровня.
Как скопировать корневой элемент, когда его поддеревья уже являются максимальными кучами
Верхний элемент - это не максимальная куча, но все поддеревья - это максимальная куча.
Чтобы сохранить свойство max-heap для всего дерева, нам придется нажимать 2 вниз, пока оно не достигнет своего правильного положения.
Как скопировать корневой элемент, когда его поддеревья являются максимальными кучами
Thus, to maintain the max-heap property in a tree where both sub-trees are max-heaps, we need to run heapify on the root element repeatedly until it is larger than its children or it becomes a leaf node.
We can combine both these conditions in one heapify function as
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
This function works for both the base case and for a tree of any size. We can thus move the root element to the correct position to maintain the max-heap status for any tree size as long as the sub-trees are max-heaps.
Build max-heap
To build a max-heap from any tree, we can thus start heapifying each sub-tree from the bottom up and end up with a max-heap after the function is applied to all the elements including the root element.
В случае полного дерева первый индекс нелистового узла имеет вид n/2 - 1. Все остальные узлы после этого являются листовыми и поэтому не нуждаются в нагромождении.
Итак, мы можем построить максимальную кучу как
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Создание массива и вычисление i 
Шаги по созданию максимальной кучи для сортировки кучи 
Шаги по созданию максимальной кучи для сортировки кучи 
Шаги по созданию максимальной кучи для сортировки кучи
Как показано на диаграмме выше, мы начинаем с нагромождения самых маленьких деревьев и постепенно продвигаемся вверх, пока не дойдем до корневого элемента.
Если вы все поняли до этого момента, поздравляю, вы на пути к освоению сортировки Heap.
Как работает сортировка кучи?
- Поскольку дерево удовлетворяет свойству Max-Heap, то самый большой элемент хранится в корневом узле.
- Swap: Удалите корневой элемент и поместите в конец массива (n-я позиция). Поместите последний элемент дерева (кучи) на свободное место.
- Удалить: уменьшить размер кучи на 1.
- Heapify: снова увеличьте количество корневого элемента, чтобы у нас был самый высокий элемент в корне.
- Процесс повторяется до тех пор, пока все элементы списка не будут отсортированы.
Поменять местами, удалить и скопировать
Код ниже показывает операцию.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Примеры Python, Java и C / C ++
Python Java C C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children 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 root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element heapify(arr, i, 0) arr = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Сложность сортировки кучи
Сортировка кучи имеет O(nlog n)временную сложность для всех случаев (лучший случай, средний случай и худший случай).
Давайте разберемся, почему. Высота полного двоичного дерева, содержащего n элементов, равнаlog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Хотя у сортировки кучи есть O(n log n)временная сложность даже для худшего случая, у нее меньше приложений (по сравнению с другими алгоритмами сортировки, такими как быстрая сортировка, сортировка слиянием). Однако его основная структура данных, куча, может быть эффективно использована, если мы хотим извлечь наименьшее (или наибольшее) из списка элементов без накладных расходов на сохранение оставшихся элементов в отсортированном порядке. Например, для очередей приоритета.
