Ebben az oktatóanyagban megtudhatja, hogyan működik a halom rendezési algoritmus. A halom rendezésére működő példákat is talál C, C ++, Java és Python nyelven.
A Heap Sort egy népszerű és hatékony rendezési algoritmus a számítógépes programozásban. A halomfajta algoritmus megírásának megtanulása kétféle adatstruktúra - tömbök és fák - ismeretét igényli.
A rendezni kívánt kezdeti számkészlet egy tömbben van tárolva, pl. Rendezés (10, 3, 76, 34, 23, 32)után rendezett tömböt kapunk(3,10,23,32,34,76)
A halom rendezés úgy működik, hogy a tömb elemeit különféle teljes bináris faként, halomnak nevezi.
Feltételként ismernie kell a teljes bináris fa és halom adatstruktúrát.
A tömbindexek és a faelemek kapcsolata
A teljes bináris fának érdekes tulajdonsága van, amelyet felhasználhatunk bármely csomópont gyermekeinek és szüleinek megkeresésére.
Ha a tömb bármely elemének indexe i, 2i+1akkor az index eleme bal gyermek lesz , az index eleme 2i+2pedig a jobb gyermek. Az i index bármely elemének szülőjét megadja az (i-1)/2.
A tömb- és kupacindexek kapcsolata
Próbáljuk ki,
1 bal gyermeke (0 index) = elem a (2 * 0 + 1) indexben = elem az 1 indexben = 12 Az 1 jobb gyermeke = elem (2 * 0 + 2) indexben = elem a 2 indexben = 9 Hasonlóképpen, 12 bal bal gyermeke (index 1) = elem a (2 * 1 + 1) indexben = elem a 3 indexben = 5 12 jobb oldali gyermeke = elem a (2 * 1 + 2) indexben = elem a 4 indexben = 6
Erősítsük meg azt is, hogy a szabályok érvényesek bármely csomópont szülőjének megtalálásához
9 szülő (2. pozíció) = (2-1) / 2 = ½ = 0.5 ~ 0 index = 1 12 szülő szülő (1. pozíció) = (1-1) / 2 = 0 index = 1
A tömbindexek fa pozíciókhoz való hozzárendelésének megértése elengedhetetlen annak megértéséhez, hogy a kupac adatstruktúra hogyan működik, és hogyan használják a kupac rendezés megvalósítására.
Mi az a halom adatszerkezete?
A halom egy speciális faalapú adatszerkezet. Állítólag egy bináris fa halom adatszerkezetet követ, ha
- ez egy teljes bináris fa
- A fa minden csomópontja azt a tulajdonságot követi, hogy nagyobbak, mint a gyermekeik, vagyis a legnagyobb elem a gyökérnél van, mind a gyermekei, mind pedig a gyökérnél kisebbek, és így tovább. Az ilyen kupacot max-kupacnak nevezzük. Ha ehelyett minden csomópont kisebb, mint a gyermekeik, akkor min-halomnak hívják
Az alábbi példa a Max-Heap és a Min-Heap ábrákat mutatja.
Max Heap és Min Heap
Ha többet szeretne megtudni róla, látogasson el a Heap Data Structure oldalra.
Hogyan lehet "felhalmozni" egy fát
A teljes bináris fáról kiindulva úgy módosíthatjuk, hogy Max-Heap legyen, ha a kupac összes nem levél elemén futtatunk egy heapify nevű függvényt.
Mivel a heapify rekurziót használ, nehéz lehet megérteni. Gondoljunk tehát először arra, hogyan halmozná fel a fát csak három elemmel.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify alapesetek
A fenti példa két forgatókönyvet mutat be - az egyikben a gyökér a legnagyobb elem, és nem kell semmit sem tennünk. És egy másik, amelyben a gyökérnek gyerekként nagyobb eleme volt, és cserélnünk kellett a max-halom tulajdonság fenntartása érdekében.
Ha korábban rekurzív algoritmusokkal dolgozott, valószínűleg felismerte, hogy ennek kell lennie az alapesetnek.
Gondoljunk most egy másik forgatókönyvre, amelyben több szint is létezik.
Hogyan lehet felhalmozni a gyökér elemet, amikor annak alfái már max halmok
A legfelső elem nem max kupac, de az összes alfa max kupac.
Az egész fa max-heap tulajdonságának fenntartásához folyamatosan 2-t kell lefelé nyomnunk, amíg el nem éri a helyes helyzetét.
Hogyan lehet felhalmozni a gyökérelemet, ha annak részfái max-halmok
Így ahhoz, hogy fenntartsuk a max-heap tulajdonságot egy olyan fán, ahol mindkét alfa max-kupac, ismételten futtatnunk kell a root elemet, amíg az nagyobb lesz, mint a gyermekei, vagy levélcsomópont lesz belőle.
Kombinálhatjuk ezeket a feltételeket egy kupacfunkcióban
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); ) )
Ez a funkció mind az alap esetre, mind bármilyen méretű fára működik. Így a gyökérelemet a megfelelő pozícióba tudjuk helyezni, hogy fenntartsuk a max-heap állapotot bármilyen fa méretnél, mindaddig, amíg az alfák max-kupacok.
Építsen max-kupacot
Bármely fáról max-halom felépítéséhez megkezdhetjük az egyes részfák halmozását alulról felfelé, és a végén egy max-halommal, miután a függvényt alkalmazzuk minden elemre, beleértve a gyökér elemet is.
Egy teljes fa esetén a nem levél csomópont első indexét a n/2 - 1. Az összes többi csomópont ezután levélcsomópont, ezért nem kell őket halmozni.
Tehát maximális halmot építhetünk
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Tömb létrehozása és i kiszámítása 
Lépések a halom rendezésének 
maximális halmának felépítéséhez Lépések a halom rendezés 
max halmának felépítéséhez
Amint a fenti ábra mutatja, a legalacsonyabb legkisebb fák halmozásával kezdjük, és fokozatosan haladunk felfelé, amíg el nem érjük a gyökérelemet.
Ha eddig mindent megértettél, gratulálok, akkor haladsz a Halom fajta elsajátításában.
Hogyan működik a halom rendezés?
- Mivel a fa kielégíti a Max-Heap tulajdonságot, a legnagyobb elemet a gyökércsomópont tárolja.
- Csere: Távolítsa el a gyökérelemet, és tegye a tömb végére (n. Pozíció) Tegye a fa utolsó elemét (kupacot) az üres helyre.
- Eltávolítás: Csökkentse a kupac méretét 1-gyel.
- Heapify: Heapify a root elemet újra, hogy a legmagasabb elem legyen a rootban.
- A folyamat addig ismétlődik, amíg a lista összes elemét rendezni nem kell.
Cserélje, távolítsa el és fejlessze
Az alábbi kód a műveletet mutatja.
// 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); )
Példák Python, Java és 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); )
Halom rendezés komplexitás
A Heap Sort O(nlog n)az összes esetre (a legjobb, átlagos és a legrosszabb esetre) bonyolult idővel rendelkezik .
Értsük meg, miért. Az n elemet tartalmazó teljes bináris fa magassága: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.
Bár a Heap Sort O(n log n)még a legrosszabb esetben is bonyolult idővel rendelkezik, nincs több alkalmazása (összehasonlítva más rendezési algoritmusokkal, mint a Quick Sort, Merge Sort). Ennek alapjául szolgáló adatstruktúrája, a halom azonban hatékonyan felhasználható, ha a legkisebbet (vagy a legnagyobbat) ki akarjuk vonni a tételek listájából anélkül, hogy a fennmaradó tételek rendezett sorrendben maradnának. Például a kiemelt várólistákra.
