V tej vadnici boste izvedeli, kako deluje algoritem za razvrščanje kopice. Prav tako boste našli delovne primere razvrščanja kopice v C, C ++, Java in Python.
Heap Sort je priljubljen in učinkovit algoritem za razvrščanje pri računalniškem programiranju. Za učenje pisanja algoritma za razvrščanje kopice je potrebno znanje o dveh vrstah podatkovnih struktur - matrike in drevesa.
Začetni nabor števil, ki ga želimo razvrstiti, je shranjen v matriki, npr. (10, 3, 76, 34, 23, 32)Po razvrščanju dobimo razvrščeno polje(3,10,23,32,34,76)
Razvrščanje kopice deluje tako, da elemente polja vizualizira kot posebno vrsto popolnega binarnega drevesa, imenovanega kopica.
Kot predpogoj morate poznati celotno strukturo podatkov binarnega drevesa in kopice.
Povezava med indeksi nizov in drevesnimi elementi
Popolno binarno drevo ima zanimivo lastnost, s katero lahko poiščemo otroke in starše katerega koli vozlišča.
Če je indeks katerega koli elementa v matriki i, bo element v indeksu 2i+1postal levi podrejeni element in element v 2i+2indeksu bo postal pravi podrejeni. Nadrejeni element katerega koli elementa v indeksu i je podan z spodnjo mejo (i-1)/2.
Povezava med indeksi nizov in kopice
Preizkusimo,
Levi podrejeni element 1 (indeks 0) = element v (2 * 0 + 1) indeks = element v 1 indeksu = 12 Desni podrejeni element 1 = element v (2 * 0 + 2) indeks = element v 2 indeksu = 9 Podobno, Levi podrejeni otrok 12 (indeks 1) = element v (2 * 1 + 1) indeks = element v 3 indeksu = 5 Desni podrejen 12 = element v (2 * 1 + 2) indeks = element v 4 indeksu = 6
Potrdimo tudi, da veljajo pravila za iskanje nadrejenega katerega koli vozlišča
Starš 9 (položaj 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Starš 12 (položaj 1) = (1-1) / 2 = 0 indeks = 1
Razumevanje tega preslikavanja indeksov polj v drevesne položaje je ključnega pomena za razumevanje, kako deluje struktura podatkovnih podatkov kopice in kako se uporablja za izvajanje razvrščanja kopice.
Kaj je struktura podatkov o kopici?
Kup je posebna podatkovna struktura, ki temelji na drevesu. Binarno drevo naj bi sledilo strukturi podatkov kopice, če
- je popolno binarno drevo
- Vsa vozlišča v drevesu sledijo lastnosti, da so večja od svojih otrok, tj. Največji element je v korenu in njegovih podrejenih ter manjši od korena itd. Tak kup se imenuje max-heap. Če so namesto tega vsa vozlišča manjša od njihovih otrok, se imenuje min-heap
Naslednji diagram prikazuje Max-Heap in Min-Heap.
Max Heap in Min Heap
Če želite izvedeti več o tem, obiščite Heap Data Structure.
Kako "zrušiti" drevo
Od popolnega binarnega drevesa ga lahko spremenimo, da postane Max-Heap, tako da zaženemo funkcijo, imenovano heapify, na vseh nelistnih elementih kupa.
Ker heapify uporablja rekurzijo, ga je težko dojeti. Torej, najprej pomislimo, kako bi drevo zgostili s samo tremi elementi.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Omogoči osnovne primere
Zgornji primer prikazuje dva scenarija - enega, pri katerem je koren največji element in nam ni treba storiti ničesar. In še en, pri katerem je imel koren v otroštvu večji element in smo ga morali zamenjati, da smo ohranili lastnost max-heap.
Če ste že delali z rekurzivnimi algoritmi, ste verjetno ugotovili, da mora biti to osnovni primer.
Zdaj pa pomislimo na drug scenarij, v katerem obstaja več kot ena raven.
Kako zgraditi korenski element, ko so njegova poddrevesa že največja gomila
Zgornji element ni max-heap, vendar so vsa poddrevesa max-heap.
Da bi ohranili lastnost max-heap za celotno drevo, bomo morali še naprej pritiskati 2 navzdol, dokler ne doseže pravilnega položaja.
Kako zgraditi korenski element, ko so njegova drevesa max-kup
Če želimo torej ohraniti lastnost max-heap v drevesu, kjer sta obe poddrevesi največji kup, moramo večkrat zagnati heapify na korenskem elementu, dokler ni večji od njegovih podrejenih ali postane vozlišče listov.
Oba pogoja lahko združimo v eno funkcijo zgoščevanja kot
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); ) )
Ta funkcija deluje tako za osnovni primer kot za drevo katere koli velikosti. Tako lahko korenski element premaknemo v pravilen položaj, da ohranimo stanje največjega kopičenja za katero koli velikost drevesa, če so poddrevesa največja gomila.
Zgradite max-heap
Če želite zgraditi max-heap iz katerega koli drevesa, lahko tako začnemo z zbiranjem vsakega poddrevesa od spodaj navzgor in končamo z max-heap, potem ko je funkcija uporabljena za vse elemente, vključno s korenskim elementom.
V primeru popolnega drevesa je prvi indeks nelistnega vozlišča podan z n/2 - 1. Vsa druga vozlišča po tem so listnata vozlišča, zato jih ni treba gnečiti.
Torej, lahko zgradimo največ kup kot
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Ustvari matriko in izračunaj i 
Koraki za gradnjo največjega kupa za razvrščanje kopice 
Koraki za gradnjo največjega kopca za sortiranje kopice 
Koraki za gradnjo največjega kupa za razvrščanje kupa
Kot je prikazano na zgornjem diagramu, začnemo z zgoščevanjem najmanjših dreves in se postopoma premikamo navzgor, dokler ne pridemo do koreninskega elementa.
Če ste vse do tukaj razumeli, čestitke, ste na poti do obvladovanja vrste kup.
Kako deluje sortiranje kopice?
- Ker drevo izpolnjuje lastnost Max-Heap, je največji element shranjen v korenskem vozlišču.
- Zamenjava: Odstranite korenski element in ga postavite na konec matrike (n-ti položaj) Na prazno mesto postavite zadnji element drevesa (kup).
- Odstrani: Velikost kupa zmanjšajte za 1.
- Heapify: koreninski element ponovno ognemo, tako da imamo najvišji element v korenu.
- Postopek se ponavlja, dokler niso razvrščeni vsi elementi na seznamu.
Zamenjajte, odstranite in Heapify
Spodnja koda prikazuje delovanje.
// 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); )
Primeri Python, Java in 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); )
Kompleksnost razvrščanja kopij
Heap Sort ima O(nlog n)časovne zapletenosti za vse primere (najboljši primer, povprečni primer in najslabši primer).
Razumimo razlog. Višina celotnega binarnega drevesa, ki vsebuje n elementov, 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.
Čeprav ima Heap Sort O(n log n)časovno zapletenost tudi v najslabšem primeru, nima več aplikacij (v primerjavi z drugimi algoritmi za razvrščanje, kot sta Quick Sort, Merge Sort). Vendar pa lahko njegovo osnovno podatkovno strukturo, kup, učinkovito uporabimo, če želimo iz seznama elementov izluščiti najmanjši (ali največji), ne da bi preostali elementi ohranili v urejenem vrstnem redu. Na primer za prednostne čakalne vrste.
