In deze tutorial leer je hoe het heap-sorteeralgoritme werkt. Ook vindt u werkende voorbeelden van heap-sortering in C, C ++, Java en Python.
Heap Sort is een populair en efficiënt sorteeralgoritme in computerprogrammering. Leren hoe het heap-sorteeralgoritme moet worden geschreven, vereist kennis van twee soorten datastructuren: arrays en bomen.
De eerste reeks getallen die we willen sorteren, wordt opgeslagen in een array, bijvoorbeeld (10, 3, 76, 34, 23, 32)en na het sorteren krijgen we een gesorteerde array(3,10,23,32,34,76)
Heap-sortering werkt door de elementen van de array te visualiseren als een speciaal soort complete binaire boom, een heap genaamd.
Als vereiste moet u op de hoogte zijn van een complete binaire boom- en heapgegevensstructuur.
Relatie tussen array-indexen en boomelementen
Een complete binaire boom heeft een interessante eigenschap die we kunnen gebruiken om de kinderen en ouders van elk knooppunt te vinden.
Als de index van een element in de array i is, wordt het element in de index 2i+1het linkerkind en het element in de 2i+2index het rechterkind. Ook wordt de ouder van elk element op index i gegeven door de ondergrens van (i-1)/2.
Verband tussen array- en heap-indices
Laten we het uittesten,
Linker child van 1 (index 0) = element in (2 * 0 + 1) index = element in 1 index = 12 Rechter child van 1 = element in (2 * 0 + 2) index = element in 2 index = 9 Evenzo, Linker child van 12 (index 1) = element in (2 * 1 + 1) index = element in 3 index = 5 Rechter child van 12 = element in (2 * 1 + 2) index = element in 4 index = 6
Laten we ook bevestigen dat de regels gelden voor het vinden van een ouder van een knooppunt
Ouder van 9 (positie 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Ouder van 12 (positie 1) = (1-1) / 2 = 0 index = 1
Het begrijpen van deze toewijzing van array-indexen aan boomposities is van cruciaal belang om te begrijpen hoe de Heap-gegevensstructuur werkt en hoe deze wordt gebruikt om Heap Sort te implementeren.
Wat is Heap-gegevensstructuur?
Heap is een speciale boomgebaseerde datastructuur. Een binaire boom zou een heap-datastructuur volgen als
- het is een complete binaire boom
- Alle knooppunten in de boom volgen de eigenschap dat ze groter zijn dan hun kinderen, dwz het grootste element bevindt zich aan de wortel en zowel zijn kinderen als kleiner dan de wortel enzovoort. Zo'n hoop wordt een max-heap genoemd. Als in plaats daarvan alle knooppunten kleiner zijn dan hun kinderen, wordt dit een min-heap genoemd
Het volgende voorbeelddiagram toont Max-Heap en Min-Heap.
Max Heap en Min Heap
Bezoek Heap Data Structure voor meer informatie.
Hoe een boom te "ophopen"
Uitgaande van een complete binaire boom, kunnen we deze wijzigen om een Max-Heap te worden door een functie genaamd heapify uit te voeren op alle niet-bladelementen van de heap.
Omdat heapify recursie gebruikt, kan het moeilijk te bevatten zijn. Laten we dus eerst eens kijken hoe u een boom zou stapelen met slechts drie elementen.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify basisscases
Het bovenstaande voorbeeld toont twee scenario's: een waarin de root het grootste element is en we niets hoeven te doen. En een andere waarin de root een groter element had als kind en we moesten wisselen om de eigenschap max-heap te behouden.
Als je eerder met recursieve algoritmen hebt gewerkt, heb je waarschijnlijk vastgesteld dat dit het basisscenario moet zijn.
Laten we nu eens kijken naar een ander scenario waarin er meer dan één niveau is.
Hoe root-element te heapificeren wanneer de substructuren ervan al maximale hopen zijn
Het bovenste element is geen max-heap, maar alle sub-trees zijn max-heap.
Om de eigenschap max-heap voor de hele boom te behouden, zullen we 2 naar beneden moeten blijven duwen totdat deze de juiste positie bereikt.
Hoe root-element te heapificeren wanneer de substructuren ervan max-heaps zijn
Dus om de eigenschap max-heap te behouden in een boom waarin beide subbomen max-hopen zijn, moeten we heapify herhaaldelijk op het root-element uitvoeren totdat het groter is dan zijn kinderen of het een bladknooppunt wordt.
We kunnen beide voorwaarden combineren in één heapify-functie als
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); ) )
Deze functie werkt zowel voor het basisgeval als voor een boom van elke grootte. We kunnen dus het root-element naar de juiste positie verplaatsen om de max-heap-status te behouden voor elke boomgrootte, zolang de sub-trees max-heaps zijn.
Bouw max-heap
Om een max-heap van elke boom te bouwen, kunnen we dus beginnen met het ophopen van elke subboom van onder naar boven en eindigen met een max-heap nadat de functie is toegepast op alle elementen, inclusief het root-element.
In het geval van een volledige boom wordt de eerste index van een niet-bladknooppunt gegeven door n/2 - 1. Alle andere knooppunten daarna zijn bladknooppunten en hoeven dus niet te worden heapified.
We kunnen dus een maximale hoop bouwen als
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Maak een array en bereken i 
Stappen om de maximale heap voor heap-sortering 
te bouwen Stappen om de maximale heap voor heap-sortering 
te bouwen Stappen om de maximale heap voor heap-sortering te bouwen
Zoals te zien is in het bovenstaande diagram, beginnen we met het stapelen van de laagste kleinste bomen en gaan we geleidelijk omhoog totdat we het wortelelement bereiken.
Als je alles tot hier hebt begrepen, gefeliciteerd, ben je op weg om de Heap-soort onder de knie te krijgen.
Hoe Heap Sort werkt?
- Omdat de boom voldoet aan de Max-Heap-eigenschap, wordt het grootste item opgeslagen op het hoofdknooppunt.
- Swap: Verwijder het root-element en plaats het aan het einde van de array (nde positie). Zet het laatste item van de boom (heap) op de vrije plaats.
- Verwijderen: verkleinen van de hoop met 1.
- Heapify: Heapify het root-element opnieuw zodat we het hoogste element bij root hebben.
- Het proces wordt herhaald totdat alle items van de lijst zijn gesorteerd.
Swap, Remove en Heapify
De onderstaande code toont de werking.
// 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 en C / C ++ voorbeelden
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); )
Heap Sort Complexiteit
Heap Sort heeft O(nlog n)tijdcomplexiteit voor alle gevallen (beste case, gemiddelde case en worst case).
Laten we de reden begrijpen waarom. De hoogte van een complete binaire boom met n elementen islog 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.
Hoewel Heap Sort O(n log n)zelfs in het ergste geval tijdcomplexiteit heeft , heeft het niet meer toepassingen (vergeleken met andere sorteeralgoritmen zoals Quick Sort, Merge Sort). De onderliggende gegevensstructuur, heap, kan echter efficiënt worden gebruikt als we de kleinste (of grootste) uit de lijst met items willen extraheren zonder de overhead van het bewaren van de resterende items in de gesorteerde volgorde. Voor bijvoorbeeld prioriteitswachtrijen.
