У овом упутству ћете научити како функционише алгоритам сортирања гомиле. Такође, наћи ћете радне примере сортирања гомиле у Ц, Ц ++, Јава и Питхон.
Хеап Сорт је популаран и ефикасан алгоритам сортирања у рачунарском програмирању. Да бисте научили како писати алгоритам сортирања гомиле, потребно је познавање две врсте структура података - низова и стабала.
Почетни скуп бројева које желимо да сортирамо чува се у низу, нпр. (10, 3, 76, 34, 23, 32)И након сортирања добијамо сортирани низ(3,10,23,32,34,76)
Сортирање хрпе функционише тако што визуализује елементе низа као посебну врсту комплетног бинарног стабла које се назива хрпа.
Као предуслов, морате знати о комплетној структури података бинарног стабла и гомиле.
Веза између индекса низа и елемената стабла
Комплетно бинарно стабло има занимљиво својство помоћу којег можемо пронаћи децу и родитеље било којег чвора.
Ако је индекс било ког елемента у низу и, елемент у индексу 2i+1постаће лево дете, а елемент у 2i+2индексу право дете. Такође, родитељ било ког елемента у индексу и дат је доњом границом од (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
Разумевање овог мапирања индекса низова на позиције стабла је пресудно за разумевање како функционише структура података гомиле и како се користи за примену сортирања гомиле.
Шта је структура података гомиле?
Хеап је посебна структура података заснована на стаблу. Каже се да бинарно стабло следи структуру података гомиле ако
- то је комплетно бинарно стабло
- Сви чворови у дрвету прате својство да су већи од своје деце, тј. Највећи елемент је у корену и оба његова детета и мањи од корена итд. Таква гомила назива се мак-гомила. Ако су уместо тога сви чворови мањи од њихове деце, то се назива мин-гомила
Следећи пример дијаграма приказује Мак-Хеап и Мин-Хеап.
Мак Хеап и Мин Хеап
Да бисте сазнали више о томе, посетите структуру података гомиле.
Како се "гомила" дрво
Полазећи од комплетног бинарног стабла, можемо га модификовати тако да постане Мак-Хеап покретањем функције која се назива хеапифи на свим нелистним елементима гомиле.
Пошто хеапифи користи рекурзију, може бити тешко схватити. Па хајде да прво размислимо о томе како бисте стабло нагомилали са само три елемента.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Хеапифи основни случајеви
Горњи пример приказује два сценарија - један у коме је корен највећи елемент и не треба ништа да радимо. И још једна у којој је корен имао већи елемент као дете и морали смо да га заменимо како бисмо одржавали својство мак-хеап.
Ако сте раније радили са рекурзивним алгоритмима, вероватно сте утврдили да ово мора бити основни случај.
Сада размислимо о другом сценарију у којем постоји више од једног нивоа.
Како гомилати основни елемент када су његова подстабла већ максимална гомила
Горњи елемент није мак-хеап, али сва подстабла су мак-гомиле.
Да бисмо задржали својство мак-хеап за цело дрво, мораћемо да притиснемо 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); 
Направите низ и израчунајте и 
Кораци за изградњу макс. Гомиле за сортирање гомиле 
Кораци за изградњу макс. Гомиле за сортирање гомиле 
Кораци за изградњу макс. Гомиле за сортирање гомиле
Као што је приказано на горњем дијаграму, започињемо гомилањем најмањих стабала и постепено се крећемо према горе док не дођемо до елемента корена.
Ако сте све разумели до овде, честитамо, на путу сте да савладате сорту Хеап.
Како сортирање гомиле функционише?
- Будући да стабло задовољава својство Мак-Хеап, тада се највећа ставка чува у коренском чвору.
- Размена: Уклоните основни елемент и ставите на крај низа (н-та позиција) Ставите последњу ставку стабла (гомилу) на упражњено место.
- Уклони: Смањите величину гомиле за 1.
- Хеапифи: Поново појачајте коренски елемент тако да имамо највиши елемент у корену.
- Поступак се понавља док се све ставке на листи не сортирају.
Замените, уклоните и Хеапифи
Код испод приказује операцију.
// 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); )
Примери за Питхон, Јава и Ц / Ц ++
Питхон Јава Ц Ц ++ # 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)временску сложеност за све случајеве (најбољи случај, просечни случај и најгори случај).
Да разумемо разлог зашто. Висина комплетног бинарног стабла које садржи н елемената је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)сортирање гомиле има временску сложеност чак и у најгорем случају, нема више апликација (у поређењу са другим алгоритмима за сортирање, попут брзог сортирања, спајања сортирања). Међутим, његова основна структура података, гомила, може се ефикасно користити ако желимо да извучемо најмањи (или највећи) са листе ставки, а да се преостали предмети не задржавају у сортираном редоследу. На пример, Приоритетни редови.
