Tässä opetusohjelmassa opit, kuinka kasan lajittelualgoritmi toimii. Löydät myös toimivia esimerkkejä kasan lajittelusta C, C ++, Java ja Python.
Heap Sort on suosittu ja tehokas lajittelualgoritmi tietokoneohjelmoinnissa. Kasan lajittelualgoritmin kirjoittamisen oppiminen edellyttää kahden tyyppisten tietorakenteiden - matriisien ja puiden - tuntemista.
Alkuperäinen numerosarja, jonka haluamme lajitella, on tallennettu taulukkoon esim. (10, 3, 76, 34, 23, 32)Lajittelun jälkeen saadaan lajiteltu taulukko(3,10,23,32,34,76)
Heap sort toimii visualisoimalla matriisin elementit erityisenä täydellisenä binäärinä puuna, jota kutsutaan kasaksi.
Edellytyksenä sinun on tiedettävä täydellisestä binääripuusta ja kasan tietorakenteesta.
Taulukkoindeksien ja puuelementtien suhde
Täydellisellä binääripuulla on mielenkiintoinen ominaisuus, jonka avulla voimme löytää minkä tahansa solmun lapset ja vanhemmat.
Jos matriisin minkä tahansa elementin indeksi on i, indeksin elementistä 2i+1tulee vasen lapsi ja 2i+2indeksin elementistä oikea lapsi. Myös indeksin i minkä tahansa elementin vanhemman antaa alaraja (i-1)/2.
Taulukko- ja kasaindeksien suhde
Testataan se,
1: n vasen lapsi (indeksi 0) = elementti (2 * 0 + 1) -hakemistossa = elementti 1-indeksissä = 12 Oikea lapsi 1 = elementti (2 * 0 + 2) -hakemistossa = elementti 2-indeksissä = 9 Samoin 12: n vasen lapsi (indeksi 1) = elementti (2 * 1 + 1) -hakemistossa = elementti 3-indeksissä = 5 Oikea 12-vuotias lapsi = elementti (2 * 1 + 2) -hakemistossa = elementti 4-indeksissä = 6
Vahvistetaan myös, että säännöt koskevat minkä tahansa solmun vanhemman löytämistä
Vanhempi 9: stä (asema 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeksi = 1 Vanhempi 12: sta (asema 1) = (1-1) / 2 = 0 indeksi = 1
Taulukkoindeksien kartoituksen ymmärtäminen puun sijainteihin on kriittistä, jotta ymmärrämme, kuinka kasan tietorakenne toimii ja miten sitä käytetään kasan lajittelun toteuttamiseen.
Mikä on kasan tietorakenne?
Heap on erityinen puupohjainen tietorakenne. Binaaripuun sanotaan noudattavan kasan tietorakennetta, jos
- se on täydellinen binääripuu
- Kaikki puun solmut seuraavat omaisuutta, että ne ovat suurempia kuin heidän lapsensa, eli suurin osa on juuressa ja molemmat sen lapset ja pienempiä kuin juuri ja niin edelleen. Tällaista kasaa kutsutaan max-kasaksi. Jos sen sijaan kaikki solmut ovat pienempiä kuin heidän lapsensa, sitä kutsutaan min-kasaksi
Seuraava esimerkkikaavio näyttää Max-Heap ja Min-Heap.
Max Heap ja Min Heap
Saat lisätietoja käymällä kasan tietorakenteessa.
Kuinka "kasata" puuta
Alkaen täydellisestä binääripuusta, voimme muokata sitä Max-Heapiksi suorittamalla heapify-funktion kaikilla kasan ei-lehtielementeillä.
Koska heapify käyttää rekursiota, sitä voi olla vaikea ymmärtää. Joten mietitään ensin, kuinka voisit kasata puun vain kolmella elementillä.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify perustapauksia
Yllä olevassa esimerkissä on kaksi skenaariota - yksi, jossa juuri on suurin elementti, eikä meidän tarvitse tehdä mitään. Ja toinen, jossa juurella oli suurempi elementti lapsena, ja meidän täytyi vaihtaa ylläpitääksemme maksimaalisen kasan ominaisuutta.
Jos olet työskennellyt rekursiivisten algoritmien kanssa aiemmin, olet todennäköisesti havainnut, että tämän on oltava perustapaus.
Ajatelkaamme nyt toista skenaariota, jossa on enemmän kuin yksi taso.
Kuinka kerätä juurielementti, kun sen alipuut ovat jo suuria kasoja
Yläosa ei ole max-kasa, mutta kaikki alipuut ovat max-kasoja.
Jotta koko puun maksimipitoisuus säilyisi, joudumme jatkuvasti työntämään 2 alaspäin, kunnes se saavuttaa oikean asennon.
Kuinka kerätä juurielementti, kun sen alipuut ovat max-kasoja
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.
Koko puun tapauksessa ei-lehtisolmun ensimmäisen indeksin antaa n/2 - 1. Kaikki muut solmut sen jälkeen ovat lehtisolmuja, joten niitä ei tarvitse kasata.
Joten voimme rakentaa maksimaalisen kasan
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Luo taulukko ja laske i 
Vaiheet rakentaa eniten kasaa kasan lajittelulle 
Vaiheet rakentaa enin kasa kasan lajittelulle 
Vaiheet rakentaa enimmälle kasalle kasan lajittelulle
Kuten yllä olevassa kaaviossa on esitetty, aloitetaan kasaamalla pienimmät pienimmät puut ja siirrymme vähitellen ylöspäin, kunnes saavutamme juurielementin.
Jos olet ymmärtänyt kaiken tähän asti, onnittelut, olet matkalla hallitsemaan kasan lajiketta.
Kuinka kasan lajittelu toimii?
- Koska puu täyttää Max-Heap -ominaisuuden, suurin kohde tallennetaan juurisolmuun.
- Vaihda: Poista juurielementti ja laita matriisin loppuun (n. Paikka) Laita puun viimeinen osa (kasa) tyhjään paikkaan.
- Poista: Pienennä kasan kokoa yhdellä.
- Heapify: Kasvata juurielementti uudelleen niin, että meillä on korkein elementti juuressa.
- Prosessi toistetaan, kunnes kaikki luettelon kohteet on lajiteltu.
Vaihda, poista ja kasaa
Alla oleva koodi näyttää toiminnon.
// 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- ja C / C ++ -esimerkkejä
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); )
Kasan lajittelun monimutkaisuus
Heap Lajittelussa on O(nlog n)aika monimutkaisuus kaikissa tapauksissa (paras tapaus, keskimääräinen tapaus ja pahin tapaus).
Ymmärretään syy miksi. N elementtiä sisältävän kokonaisen binääripuun korkeus onlog 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.
Vaikka kasan lajittelulla on O(n log n)aika monimutkaisuus jopa pahimmassa tapauksessa, sillä ei ole enemmän sovelluksia (verrattuna muihin lajittelualgoritmeihin, kuten Quick Sort, Merge Sort). Sen taustalla olevaa tietorakennetta, kasaa, voidaan kuitenkin käyttää tehokkaasti, jos haluamme poimia pienimmän (tai suurimman) esineiden luettelosta ilman lisäkustannuksia, kun muut kohteet pidetään lajiteltuina. Esimerkiksi prioriteettijonot.
