В този урок ще научите как работи алгоритъмът за сортиране на купчини. Също така ще намерите работни примери за сортиране на купчини в 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) индекс = елемент в 1 индекс = 12 Десно дъщерно на 1 = елемент в (2 * 0 + 2) индекс = елемент в 2 индекс = 9 По същия начин, Ляво дете на 12 (индекс 1) = елемент в (2 * 1 + 1) индекс = елемент в 3 индекс = 5 Дясно дете на 12 = елемент в (2 * 1 + 2) индекс = елемент в 4 индекс = 6
Нека също така потвърдим, че важат правилата за намиране на родител на който и да е възел
Родител на 9 (позиция 2) = (2-1) / 2 = ½ = 0,5 ~ 0 индекс = 1 Родител на 12 (позиция 1) = (1-1) / 2 = 0 индекс = 1
Разбирането на това картографиране на индексите на масиви в позиции на дърво е от решаващо значение за разбирането как работи структурата на данните от купчината и как се използва за реализиране на сортиране на купчини.
Какво представлява структурата на данните за купчина?
Heap е специална структура на данни, базирана на дърво. Казва се, че двоично дърво следва структурата от данни на куп, ако
- това е пълно двоично дърво
- Всички възли в дървото следват свойството, че са по-големи от техните деца, т.е. най-големият елемент е в корена и неговите деца, и по-малък от корена и т.н. Такава купчина се нарича max-heap. Ако вместо това всички възли са по-малки от техните деца, това се нарича min-heap
Следващата примерна диаграма показва Max-Heap и Min-Heap.
Max Heap и Min Heap
За да научите повече за това, моля, посетете Heap Data Structure.
Как да "натрупвам" дърво
Започвайки от цялостно двоично дърво, можем да го модифицираме, за да се превърне в 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, но всички под-дървета са max-heap.
За да поддържаме свойството max-heap за цялото дърво, ще трябва да продължаваме да натискаме 2 надолу, докато достигне правилната си позиция.
Как да обогатявам коренния елемент, когато неговите поддървета са max-купища
По този начин, за да поддържаме свойството max-heap в дърво, където и двете поддървета са максимални купчини, трябва да стартираме heapify на кореновия елемент многократно, докато той е по-голям от неговите деца или той стане листен възел.
Можем да комбинираме и двете условия в една усилена функция като
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); ) )
Тази функция работи както за основния случай, така и за дърво с всякакъв размер. По този начин можем да преместим основния елемент в правилната позиция, за да поддържаме състоянието на максимална купчина за всеки размер на дървото, стига под-дърветата да са максимални купчини.
Изградете max-heap
За да изградим максимална купчина от всяко дърво, можем по този начин да започнем да натрупваме всяко поддърво отдолу нагоре и да завършим с максимална купчина, след като функцията бъде приложена към всички елементи, включително основния елемент.
В случай на пълно дърво, първият индекс на нелистен възел се дава от n/2 - 1. Всички останали възли след това са листови възли и по този начин не е необходимо да се натрупват.
И така, можем да изградим максимална купчина като
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Създайте масив и изчислете i 
Стъпки за изграждане на максимална купчина за сортиране на купчини 
Стъпки за изграждане на максимална купчина за сортиране на купчини 
Стъпки за изграждане на максимална купчина за сортиране на купчини
Както е показано на горната диаграма, започваме с натрупване на най-малките най-малки дървета и постепенно се придвижваме нагоре, докато стигнем до кореновия елемент.
Ако сте разбрали всичко до тук, поздравления, вие сте на път да овладеете сорта Heap.
Как работи сортирането на купчини?
- Тъй като дървото отговаря на свойството Max-Heap, тогава най-големият елемент се съхранява в основния възел.
- Размяна: Премахнете основния елемент и поставете в края на масива (n-та позиция) Поставете последния елемент от дървото (купчината) на свободното място.
- Премахване: Намалете размера на купчината с 1.
- Heapify: Хепифицирайте отново кореновия елемент, така че да имаме най-високия елемент в корена.
- Процесът се повтаря, докато всички елементи от списъка бъдат сортирани.
Разменете, премахнете и 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); )
Сложност на сортирането на купчини
Heap Sort има 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.
Въпреки че Heap Sort има O(n log n)сложност във времето дори в най-лошия случай, той няма повече приложения (в сравнение с други алгоритми за сортиране като Quick Sort, Merge Sort). Въпреки това, нейната основна структура от данни, купчина, може ефективно да се използва, ако искаме да извлечем най-малката (или най-голямата) от списъка с елементи, без да се налага да запазваме останалите елементи в сортирания ред. Например за приоритетни опашки.
