Šioje pamokoje sužinosite, kaip veikia kaupo rūšiavimo algoritmas. Taip pat rasite naudingų kaupų rūšiavimo pavyzdžių C, C ++, Java ir Python.
„Heap Sort“ yra populiarus ir efektyvus kompiuterių programavimo algoritmas. Norint išmokti rašyti kaupo rūšiavimo algoritmą, reikia žinoti dviejų tipų duomenų struktūras - masyvus ir medžius.
Pradinis skaičių rinkinys, kurį norime rūšiuoti, yra saugomas masyve, pvz., (10, 3, 76, 34, 23, 32)O surūšiavus gauname surūšiuotą masyvą(3,10,23,32,34,76)
„Heap sort“ veikia vizualizuodami masyvo elementus kaip ypatingą užbaigto dvejetainio medžio rūšį, vadinamą kaupu.
Kaip būtina sąlyga, turite žinoti apie visą dvejetainio medžio ir kaupo duomenų struktūrą.
Masyvo indeksų ir medžių elementų ryšys
Visas dvejetainis medis turi įdomią savybę, kurią galime naudoti norėdami surasti bet kurio mazgo vaikus ir tėvus.
Jei kurio nors masyvo elemento indeksas yra i, indekso elementas 2i+1taps kairiuoju, o 2i+2indekso elementas - dešiniuoju. Be to, bet kurio indekso i elemento tėvą nurodo apatinė riba (i-1)/2.
Masyvo ir kaupo indeksų santykis
Išbandykime,
Kairysis vaikas iš 1 (indeksas 0) = elementas (2 * 0 + 1) rodyklėje = elementas 1 rodyklėje = 12 dešinysis 1 vaikas = elementas (2 * 0 + 2) rodyklėje = elementas 2 rodyklėje = 9 Panašiai, Kairysis 12 vaikų vaikas (1 indeksas) = elementas (2 * 1 + 1) rodyklėje = elementas 3 rodyklėje = 5 Dešinysis 12 vaikų vaikas = elementas (2 * 1 + 2) rodyklėje = elementas 4 rodyklėje = 6
Taip pat patvirtinkime, kad taisyklės galioja norint rasti bet kurio mazgo tėvą
9 tėvai (2 pozicija) = (2-1) / 2 = ½ = 0,5 ~ 0 indeksas = 1 12 tėvų (1 pozicija) = (1-1) / 2 = 0 indeksas = 1
Suprasti šį masyvo indeksų susiejimą su medžių pozicijomis yra labai svarbu norint suprasti, kaip veikia kaupo duomenų struktūra ir kaip ji naudojama įgyvendinant „Heap Sort“.
Kas yra krūvos duomenų struktūra?
Krūva yra speciali medžių duomenų struktūra. Sakoma, kad dvejetainis medis atitinka kaupo duomenų struktūrą, jei
- tai visiškas dvejetainis medis
- Visi medžio mazgai laikosi savybės, kad jie yra didesni už savo vaikus, ty didžiausias elementas yra prie šaknies ir jo vaikų, ir mažesnis už šaknį ir pan. Toks krūva vadinama „max-heap“. Jei vietoj to visi mazgai yra mažesni nei jų vaikai, tai vadinama min-kupinu
Šis diagramos pavyzdys rodo „Max-Heap“ ir „Min-Heap“.
Maks Heapas ir Min Heapas
Norėdami sužinoti daugiau apie tai, apsilankykite „Heap Data Structure“.
Kaip „kaupti“ medį
Pradėdami nuo visiško dvejetainio medžio, jį galime modifikuoti taip, kad jis taptų „Max-Heap“, vykdydami funkciją „heapify“, vadinamą visais ne lapo formos krūvos elementais.
Kadangi „Heapify“ naudoja rekursiją, tai gali būti sunku suvokti. Taigi pirmiausia pagalvokime, kaip sukaupsi medį tik su trim elementais.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Sukaupkite pagrindinius atvejus
Aukščiau pateiktame pavyzdyje parodyti du scenarijai - vienas, kuriame šaknis yra didžiausias elementas, ir mums nieko nereikia daryti. Ir dar vienas, kuriame šaknis vaikystėje turėjo didesnį elementą ir mums reikėjo sukeisti, kad išlaikytume maksimalaus kaupo savybę.
Jei anksčiau dirbote su rekursiniais algoritmais, tikriausiai nustatėte, kad tai turi būti pagrindinis atvejis.
Dabar pagalvokime apie kitą scenarijų, kuriame yra daugiau nei vienas lygis.
Kaip sukaupti šakninį elementą, kai jo potemiai jau yra maksimalūs kaupai
Viršutinis elementas nėra maksimalus kaupas, tačiau visi medžiai yra maks. Krūvos.
Norėdami išlaikyti viso medžio savybę „max-heap“, turėsime toliau stumti 2 žemyn, kol jis pasieks teisingą padėtį.
Kaip sukaupti šakninį elementą, kai jo potemiai yra maks. Krūvos
Taigi, norėdami išlaikyti „max-heap“ savybę medyje, kuriame abu medžiai yra maks. Krūvos, turime pakartotinai paleisti šaknies elementą, kol jis bus didesnis nei jo vaikai arba jis taps lapų mazgu.
Abi šias sąlygas galime sujungti į vieną kaupimo funkciją kaip
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); ) )
Ši funkcija tinka tiek pagrindiniam, tiek bet kokio dydžio medžiui. Taigi mes galime perkelti šaknies elementą į teisingą padėtį, kad išlaikytume maksimalaus kaupo būseną bet kokio medžio dydžiui, jei pogrindžiai yra maks.
Sukurkite maksimalų kaupą
Norėdami sukurti maksimalų kaupą iš bet kurio medžio, galime pradėti kaupti kiekvieną medį iš apačios į viršų ir baigti maksimaliu kaupu, pritaikius funkciją visiems elementams, įskaitant šaknies elementą.
Užbaigto medžio atveju pirmąjį ne lapo mazgo indeksą pateikia n/2 - 1. Visi kiti mazgai po to yra lapų mazgai, todėl jų nereikia kaupti.
Taigi, mes galime sukurti maksimalų kaupą
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Sukurkite masyvą ir apskaičiuokite i 
žingsnius, kad sukurtumėte maksimalų kaupą 
kaupti rūšiuoti 
žingsnius, kad sukurtumėte maksimalų kaupą kaupti rūšį.
Kaip parodyta aukščiau pateiktoje diagramoje, mes pradedame kaupti žemiausius mažiausius medžius ir palaipsniui judėti aukštyn, kol pasieksime šaknies elementą.
Jei viską supratote iki šiol, sveikiname, jūs einate įvaldyti „Heap“ rūšį.
Kaip veikia „Heap Sort“?
- Kadangi medis atitinka „Max-Heap“ ypatybę, didžiausias elementas saugomas šaknies mazge.
- Sukeisti: nuimkite šaknies elementą ir įdėkite į masyvo galą (n-oji pozicija) Į laisvą vietą įdėkite paskutinį medžio elementą (kaupą).
- Pašalinti: sumažinkite kaupo dydį 1.
- Heapify: dar kartą sukaupkite šaknies elementą, kad šaknyje būtų aukščiausias elementas.
- Procesas kartojamas tol, kol bus surūšiuoti visi sąrašo elementai.
Pakeiskite, pašalinkite ir kaupkite
Žemiau pateiktas kodas rodo operaciją.
// 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“ ir „C / C ++“ pavyzdžiai
„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); )
Krūvos rūšiavimo kompleksiškumas
„Heap Sort“ turi O(nlog n)laiko sudėtingumą visais atvejais (geriausiu, vidutiniu ir blogiausiu atveju).
Supraskime priežastis. Pilno dvejetainio medžio, kuriame yra n elementų, aukštis yralog 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.
Nors „Heap Sort“ O(n log n)net ir blogiausiu atveju yra sudėtingas laikas, jis neturi daugiau programų (palyginti su kitais rūšiavimo algoritmais, tokiais kaip „Quick Sort“, „Merge Sort“). Tačiau pagrindinę duomenų struktūrą - kaupą - galima efektyviai naudoti, jei norime iš daiktų sąrašo išskirti mažiausią (arba didžiausią) be pridėtinės vertės likusių daiktų nelaikymo rūšiuojama tvarka. Pavyzdžiui, prioritetinės eilės.
