U ovom vodiču naučit ćete kako funkcionira algoritam sortiranja hrpe. Također ćete naći radne primjere sortiranja hrpe u C, C ++, Java i Python.
Heap Sort popularan je i učinkovit algoritam sortiranja u računalnom programiranju. Da biste naučili kako pisati algoritam sortiranja hrpe, potrebno je poznavanje dvije vrste struktura podataka - nizova i stabala.
Početni skup brojeva koje želimo razvrstati pohranjen je u niz, npr. (10, 3, 76, 34, 23, 32)I nakon razvrstavanja dobivamo razvrstani niz(3,10,23,32,34,76)
Razvrstavanje hrpe djeluje vizualiziranjem elemenata niza kao posebne vrste cjelovitog binarnog stabla koje se naziva hrpa.
Kao preduvjet, morate znati o cjelovitoj strukturi podataka binarnog stabla i hrpe.
Povezanost indeksa niza s elementima stabla
Kompletno binarno stablo ima zanimljivo svojstvo pomoću kojeg možemo pronaći djecu i roditelje bilo kojeg čvora.
Ako je indeks bilo kojeg elementa u nizu i, element u indeksu 2i+1postat će lijevo dijete, a element u 2i+2indeksu postat će desno dijete. Također, roditelj bilo kojeg elementa u indeksu i dat je donjom granicom (i-1)/2.
Povezanost indeksa niza i hrpe
Isprobajmo,
Lijevo dijete 1 (indeks 0) = element u (2 * 0 + 1) indeks = element u 1 indeksu = 12 Desno dijete 1 = element u (2 * 0 + 2) indeks = element u 2 indeks = 9 Slično tome, Lijevo dijete od 12 (indeks 1) = element u (2 * 1 + 1) indeks = element u 3 indeks = 5 Desno dijete od 12 = element u (2 * 1 + 2) indeks = element u 4 indeks = 6
Potvrdimo također da vrijede pravila za pronalaženje roditelja bilo kojeg čvora
Roditelj od 9 (položaj 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Roditelj od 12 (položaj 1) = (1-1) / 2 = 0 indeks = 1
Razumijevanje ovog mapiranja indeksa nizova na položaje stabla presudno je za razumijevanje kako funkcionira struktura podataka hrpe i kako se koristi za implementaciju sortiranja hrpe.
Što je struktura podataka hrpe?
Hrpa je posebna struktura podataka koja se temelji na stablu. Kaže se da binarno stablo slijedi strukturu podataka hrpe ako
- to je potpuno binarno stablo
- Svi čvorovi u stablu slijede svojstvo da su veći od njihove djece, tj. Najveći je element u korijenu i njegova djeca i manji od korijena i tako dalje. Takva hrpa naziva se max-hrpa. Ako su umjesto toga svi čvorovi manji od njihove djece, naziva se min-hrpa
Sljedeći primjer dijagrama prikazuje Max-Heap i Min-Heap.
Max Heap i Min Heap
Da biste saznali više o tome, posjetite strukturu podataka gomile.
Kako "gomilati" drvo
Polazeći od cjelovitog binarnog stabla, možemo ga izmijeniti tako da postane Max-Heap pokretanjem funkcije koja se naziva heapify na svim ne-lisnim elementima hrpe.
Budući da heapify koristi rekurziju, može ga biti teško shvatiti. Pa prvo razmislimo o tome kako biste stablo napuhali sa samo tri elementa.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify osnovni slučajevi
Gornji primjer prikazuje dva scenarija - jedan u kojem je korijen najveći element i ne trebamo ništa raditi. I još jedan u kojem je korijen imao veći element kao dijete i morali smo ga zamijeniti da bismo održali svojstvo max-heap.
Ako ste i prije radili s rekurzivnim algoritmima, vjerojatno ste utvrdili da to mora biti osnovni slučaj.
Sada razmislimo o drugom scenariju u kojem postoji više od jedne razine.
Kako gomilati korijenski element kada su njegova podstabla već maksimalna gomila
Gornji element nije max-heap, ali sva su podstabla max-hrpe.
Da bismo zadržali svojstvo max-heap za cijelo stablo, morat ćemo nastaviti pritiskati 2 prema dolje dok ne dosegne svoj točan položaj.
Kako gomilati korijenski element kada su njegova podstabla max-hrpe
Dakle, da bismo zadržali svojstvo max-heap u stablu gdje su oba podstabla max-hrpe, moramo više puta izvoditi heapify na korijenskom elementu dok nije veći od njegove djece ili dok ne postane čvor lista.
Oba ova stanja možemo kombinirati u jednoj funkciji pojačavanja kao
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); ) )
Ova funkcija radi i za osnovni slučaj i za stablo bilo koje veličine. Tako korijenski element možemo premjestiti u ispravan položaj kako bismo zadržali status max-heap za bilo koju veličinu stabla sve dok su podstabla max-hrpe.
Izgradite max-heap
Da bismo izgradili max-hrpu od bilo kojeg stabla, tako možemo početi gomilati svako podstablo odozdo prema gore i završiti s max-heap-om nakon što se funkcija primijeni na sve elemente, uključujući korijenski element.
U slučaju cjelovitog stabla, prvi indeks nelistnog čvora dan je s n/2 - 1. Svi ostali čvorovi nakon toga su lisni čvorovi i stoga ih ne treba gomilati.
Dakle, možemo izgraditi maksimalnu hrpu kao
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Stvaranje niza i izračunavanje i 
Koraci za izgradnju maksimalne hrpe za sortiranje hrpe 
Koraci za izgradnju maksimalne hrpe za sortiranje hrpe 
Koraci za izgradnju maksimalne hrpe za sortiranje hrpe
Kao što je prikazano na gornjem dijagramu, započinjemo gomilanjem najmanjih najmanjih stabala i postupno se krećemo prema gore dok ne dođemo do korijenskog elementa.
Ako ste sve ovdje razumjeli, čestitam, na putu ste da svladate sortu Heap.
Kako sortiranje hrpe djeluje?
- Budući da stablo zadovoljava svojstvo Max-Heap, tada se najveća stavka sprema u korijenski čvor.
- Zamjena: Uklonite korijenski element i stavite na kraj niza (n-ti položaj) Stavite posljednju stavku stabla (hrpu) na slobodno mjesto.
- Ukloni: Smanjite veličinu hrpe za 1.
- Heapify: Ponovno pojačajte korijenski element tako da imamo najviši element u korijenu.
- Postupak se ponavlja dok se sve stavke popisa ne sortiraju.
Zamijenite, uklonite i pojačajte
Kôd u nastavku prikazuje operaciju.
// 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); )
Primjeri Pythona, Java i 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); )
Složenost sortiranja hrpe
Heap Sort ima O(nlog n)vremenske složenosti za sve slučajeve (najbolji slučaj, prosječni slučaj i najgori slučaj).
Razumijemo razlog zašto. Visina cjelovitog binarnog stabla koje sadrži n elemenata jelog 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.
Iako Heap Sort ima O(n log n)vremensku složenost čak i u najgorem slučaju, nema više aplikacija (u usporedbi s drugim algoritmima za sortiranje poput Quick Sort, Merge Sort). Međutim, njegova temeljna struktura podataka, gomila, može se učinkovito koristiti ako želimo izvući najmanji (ili najveći) s popisa stavki bez prekomjernog zadržavanja preostalih stavki u razvrstanom redoslijedu. Za npr. Prioritetne redove.
