I den här guiden lär du dig hur algoritmen för sortering fungerar. Du hittar också arbetsexempel på högsortering i C, C ++, Java och Python.
Heap Sort är en populär och effektiv sorteringsalgoritm inom datorprogrammering. Att lära sig att skriva algoritmen för hopsortering kräver kunskap om två typer av datastrukturer - matriser och träd.
Den ursprungliga siffran som vi vill sortera lagras i en matris, t.ex. (10, 3, 76, 34, 23, 32)och efter sortering får vi en sorterad matris(3,10,23,32,34,76)
Heap sort fungerar genom att visualisera elementen i arrayen som en speciell typ av komplett binärt träd som kallas en heap.
Som en förutsättning måste du känna till en fullständig binär träd- och högdatastruktur.
Förhållandet mellan matrisindex och trädelement
Ett komplett binärt träd har en intressant egenskap som vi kan använda för att hitta barn och föräldrar till vilken nod som helst.
Om indexet för något element i matrisen är i, blir elementet i indexet 2i+1det vänstra barnet och elementet i 2i+2indexet blir det rätta barnet. Föräldern till vilket element som helst i index i ges också av den nedre gränsen för (i-1)/2.
Förhållandet mellan array- och högindex
Låt oss testa det,
Vänster barn av 1 (index 0) = element i (2 * 0 + 1) index = element i 1 index = 12 Höger barn av 1 = element i (2 * 0 + 2) index = element i 2 index = 9 På samma sätt, Vänster barn av 12 (index 1) = element i (2 * 1 + 1) index = element i 3 index = 5 Höger barn av 12 = element i (2 * 1 + 2) index = element i 4 index = 6
Låt oss också bekräfta att reglerna gäller för att hitta förälder till vilken nod som helst
Förälder till 9 (position 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Förälder till 12 (position 1) = (1-1) / 2 = 0 index = 1
Att förstå denna kartläggning av matrisindex till trädpositioner är avgörande för att förstå hur Heap-datastrukturen fungerar och hur den används för att implementera Heap Sort.
Vad är Heap-datastruktur?
Heap är en speciell trädbaserad datastruktur. Ett binärt träd sägs följa en högdata-struktur om
- det är ett komplett binärt träd
- Alla noder i trädet följer egenskapen att de är större än sina barn, dvs. det största elementet är vid roten och både dess barn och mindre än roten och så vidare. En sådan hög kallas en max-heap. Om istället alla noder är mindre än deras barn kallas det en min-hög
Följande exempeldiagram visar Max-Heap och Min-Heap.
Max Heap och Min Heap
För att lära dig mer om det, besök Heap Data Structure.
Hur man "höger" ett träd
Med utgångspunkt från ett komplett binärt träd kan vi ändra det för att bli en Max-Heap genom att köra en funktion som heter heapify på alla icke-bladelement i högen.
Eftersom heapify använder rekursion kan det vara svårt att förstå. Så låt oss först tänka på hur du skulle kunna höja ett träd med bara tre element.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify basfall
Exemplet ovan visar två scenarier - ett där roten är det största elementet och vi behöver inte göra någonting. Och en annan där roten hade ett större element som barn och vi behövde byta för att bibehålla max-heap-egenskapen.
Om du har arbetat med rekursiva algoritmer tidigare har du förmodligen identifierat att detta måste vara basfallet.
Låt oss nu tänka på ett annat scenario där det finns mer än en nivå.
Hur man heapify rotelementet när dess underträd redan är maxhöjder
Det övre elementet är inte en maxhög men alla underträd är maxhögar.
För att bibehålla max-heap-egenskapen för hela trädet måste vi fortsätta trycka 2 nedåt tills det når rätt läge.
Hur man heapify rotelement när dess underträd är max-heaps
Således, för att bibehålla max-heap-egenskapen i ett träd där båda subträd är max-heaps, måste vi köra heapify på rotelementet upprepade gånger tills det är större än sina barn eller om det blir en bladnod.
Vi kan kombinera båda dessa villkor i en heapify-funktion som
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); ) )
Denna funktion fungerar både för basfodralet och för ett träd av alla storlekar. Vi kan alltså flytta rotelementet till rätt position för att bibehålla max-heap-statusen för alla trädstorlekar så länge som subträdarna är max-heaps.
Bygg max-heap
För att bygga en max-heap från vilket träd som helst kan vi alltså börja heapifying varje sub-träd från botten upp och sluta med en max-heap efter att funktionen har tillämpats på alla element inklusive root-elementet.
När det gäller ett komplett träd ges det första indexet för en icke-bladnod av n/2 - 1. Alla andra noder efter det är bladnoder och behöver därför inte heapifieras.
Så vi kan bygga en maximal hög som
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Skapa matris och beräkna i 
Steg för att bygga maxheap för heap sort 
Steg för att bygga max heap för heap sort 
Steg för att bygga max heap för heap sort
Som visas i ovanstående diagram börjar vi med att höja de lägsta minsta träden och rör oss gradvis upp tills vi når rotelementet.
Om du har förstått allt fram till här, grattis, du är på väg att bemästra Heap-sorten.
Hur fungerar högsortering?
- Eftersom trädet uppfyller Max-Heap-egenskapen lagras det största objektet i rotnoden.
- Byt: Ta bort rotelementet och placera i slutet av matrisen (n: e position) Sätt det sista objektet i trädet (hög) på den lediga platsen.
- Ta bort: Minska högen med 1.
- Heapify: Heapify rotelementet igen så att vi har det högsta elementet vid roten.
- Processen upprepas tills alla objekt i listan är sorterade.
Byt, ta bort och Heapify
Koden nedan visar operationen.
// 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 och C / C ++ exempel
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); )
Högsorteringskomplexitet
Heap Sort har O(nlog n)tidskomplexitet för alla fall (bästa fall, genomsnittliga fall och värsta fall).
Låt oss förstå anledningen till varför. Höjden på ett komplett binärt träd som innehåller n element ärlog 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.
Även om Heap Sort har O(n log n)tidskomplexitet även i värsta fall har det inte fler applikationer (jämfört med andra sorteringsalgoritmer som Snabbsortering, Sammanfoga sortering). Den underliggande datastrukturen, heap, kan dock användas effektivt om vi vill extrahera den minsta (eller största) från listan med objekt utan att kostnaden för att behålla de återstående objekten i sorterad ordning. För t.ex. prioritetsköer.
