Hög sort är en jämförelsebaserad sorteringsteknik baserad på Binär hög datastruktur. Det liknar urval sortera där vi först hittar minimumelementet och placerar minimumelementet i början. Upprepa samma process för de återstående elementen.
Heap Sortering Algoritm
Följ idén nedan för att lösa problemet:
Rekommenderat problem Lös det på ÖVNING först, innan du går vidare till lösningen Lös problemKonvertera först arrayen till heapdatastruktur med hjälp av heapify, radera sedan en efter en rotnoden för Max-heapen och ersätt den med den sista noden i heapen och heapifiera sedan rotnoden av heapen. Upprepa denna process tills storleken på högen är större än 1.
- Bygg en hög från den givna inmatningsmatrisen.
- Upprepa följande steg tills högen bara innehåller ett element:
- Byt ut rotelementet i högen (som är det största elementet) med det sista elementet i högen.
- Ta bort det sista elementet i högen (som nu är i rätt position).
- Förhöj de återstående elementen i högen.
- Den sorterade matrisen erhålls genom att vända ordningen på elementen i inmatningsmatrisen.
Detaljerad bearbetning av heapsortering
För att förstå högsorteringen tydligare, låt oss ta en osorterad array och försöka sortera den med hjälp av högsortering.
Tänk på arrayen: arr[] = {4, 10, 3, 5, 1}.Bygg ett komplett binärt träd: Bygg ett komplett binärt träd från arrayen.
Högsorteringsalgoritm | Bygg ett komplett binärt träd
exekvera skriptskalFörvandla till maxhög: Efter det är uppgiften att konstruera ett träd från den osorterade arrayen och försöka konvertera den till max hög.
- För att omvandla en heap till en max-heap, bör den överordnade noden alltid vara större än eller lika med undernoderna
- Här, i det här exemplet, som överordnad nod 4 är mindre än barnnoden 10, byt dem därför för att bygga en maxhög.
- Nu, 4 som förälder är mindre än barnet 5 , byt ut båda dessa igen och den resulterande heapen och arrayen bör vara så här:
Högsorteringsalgoritm | Max Heapify konstruerade binärt träd
Utför högsortering: Ta bort det maximala elementet i varje steg (dvs flytta det till ändläget och ta bort det) och överväg sedan de återstående elementen och omvandla det till en maxhög.
- Ta bort rotelementet (10) från maxhögen. För att ta bort denna nod, försök att byta ut den med den sista noden, dvs. (1). Efter att ha tagit bort rotelementet, heapify det igen för att konvertera det till max heap.
- Resulterande heap och array bör se ut så här:
Högsorteringsalgoritm | Ta bort maximum från root och max heapify
- Upprepa stegen ovan och det kommer att se ut så här:
Högsorteringsalgoritm | Ta bort nästa maximum från root nad max heapify
- Ta nu bort roten (dvs. 3) igen och utför heapify.
Högsorteringsalgoritm | Upprepa föregående steg
- Nu när roten tas bort igen är den sorterad. och den sorterade arrayen blir som arr[] = {1, 3, 4, 5, 10} .
Högsorteringsalgoritm | Slutlig sorterad array
Implementering av Heap Sort
C++ // C++ program for implementation of Heap Sort #include using namespace std; // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Initialize largest as root int largest = i; // left = 2*i + 1 int l = 2 * i + 1; // right = 2*i + 2 int r = 2 * i + 2; // If left child is larger than root if (l < N && arr[l]>arr[störst]) störst = l; // Om höger barn är större än störst // hittills om (r< N && arr[r]>arr[största]) största = r; // Om störst inte är rot if (störst != i) { swap(arr[i], arr[störst]); // Rekursivt heapify det påverkade // sub-tree heapify(arr, N, största); } } // Huvudfunktion för att göra heapsortering void heapSort(int arr[], int N) { // Bygg heap (ordna om array) för (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // En efter en extrahera ett element // från heap for (int i = N - 1; i> 0; i--) { // Flytta nuvarande rot för att avsluta swap(arr[0], arr[i]); // ring max heapify på den reducerade heapen heapify(arr, i, 0); } } // En verktygsfunktion för att skriva ut array med storlek n void printArray(int arr[], int N) { for (int i = 0; i< N; ++i) cout << arr[i] << ' '; cout << '
'; } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); cout << 'Sorted array is
'; printArray(arr, N); }> C // Heap Sort in C #include // Function to swap the position of two elements void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Find largest among root, // left child and right child // Initialize largest as root int largest = i; // left = 2*i + 1 int left = 2 * i + 1; // right = 2*i + 2 int right = 2 * i + 2; // If left child is larger than root if (left < N && arr[left]>arr[största]) största = vänster; // Om höger barn är större än störst // hittills om (höger< N && arr[right]>arr[störst]) störst = höger; // Byt och fortsätt heapifying // om roten inte är störst // Om störst inte är roten if (störst != i) { swap(&arr[i], &arr[störst]); // Rekursivt heapify det påverkade // sub-tree heapify(arr, N, största); } } // Huvudfunktion för att göra heap sort void heapSort(int arr[], int N) { // Bygg max heap för (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 rotelement // för att få högsta element vid // root igen heapify(arr, i, 0); } } // En verktygsfunktion för att skriva ut array med storlek n void printArray(int arr[], int N) { for (int i = 0; i< N; i++) printf('%d ', arr[i]); printf('
'); } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); printf('Sorted array is
'); printArray(arr, N); } // This code is contributed by _i_plus_plus_.> Java // Java program for implementation of Heap Sort public class HeapSort { public void sort(int arr[]) { int N = arr.length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // En efter en extrahera ett element från heap för (int i = N - 1; i> 0; i--) { // Flytta nuvarande rot till slutet int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // ring max heapify på den reducerade heapen heapify(arr, i, 0); } } // För att heapify ett underträd som är rotat med nod i som är // ett index i arr[]. n är storleken på heap void heapify(int arr[], int N, int i) { int största = i; // Initiera störst som rot int l = 2 * i + 1; // vänster = 2*i + 1 int r = 2 *i + 2; // höger = 2*i + 2 // Om vänster barn är större än roten om (l< N && arr[l]>arr[störst]) störst = l; // Om det högra barnet är större än det största hittills om (r< N && arr[r]>arr[största]) största = r; // Om störst inte är rot if (störst != i) { int swap = arr[i]; arr[i] = arr[störst]; arr[största] = byta; // Heapify rekursivt det påverkade underträdet heapify(arr, N, störst); } } /* En verktygsfunktion för att skriva ut array med storlek n */ static void printArray(int arr[]) { int N = arr.length; för (int i = 0; i< N; ++i) System.out.print(arr[i] + ' '); System.out.println(); } // Driver's code public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = arr.length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println('Sorted array is'); printArray(arr); } }> C# // C# program for implementation of Heap Sort using System; public class HeapSort { public void sort(int[] arr) { int N = arr.Length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // En efter en extrahera ett element från heap för (int i = N - 1; i> 0; i--) { // Flytta nuvarande rot till slutet int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // ring max heapify på den reducerade heapen heapify(arr, i, 0); } } // För att heapify ett underträd som är rotat med nod i som är // ett index i arr[]. n är storleken på heap void heapify(int[] arr, int N, int i) { int största = i; // Initiera störst som rot int l = 2 * i + 1; // vänster = 2*i + 1 int r = 2 *i + 2; // höger = 2*i + 2 // Om vänster barn är större än roten om (l< N && arr[l]>arr[störst]) störst = l; // Om det högra barnet är större än det största hittills om (r< N && arr[r]>arr[största]) största = r; // Om störst inte är rot if (störst != i) { int swap = arr[i]; arr[i] = arr[störst]; arr[största] = byta; // Heapify rekursivt det påverkade underträdet heapify(arr, N, störst); } } /* En verktygsfunktion för att skriva ut array med storlek n */ static void printArray(int[] arr) { int N = arr.Length; för (int i = 0; i< N; ++i) Console.Write(arr[i] + ' '); Console.Read(); } // Driver's code public static void Main() { int[] arr = { 12, 11, 13, 5, 6, 7 }; int N = arr.Length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); Console.WriteLine('Sorted array is'); printArray(arr); } } // This code is contributed // by Akanksha Rai(Abby_akku)> Javascript // JavaScript program for implementation // of Heap Sort function sort( arr) { var N = arr.length; // Build heap (rearrange array) for (var i = Math.floor(N / 2) - 1; i>= 0; i--) heapify(arr, N, i); // En efter en extrahera ett element från heap för (var i = N - 1; i> 0; i--) { // Flytta nuvarande rot till slutet var temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // ring max heapify på den reducerade heapen heapify(arr, i, 0); } } // Att heapify ett underträd som är rotat med nod i som är // ett index i arr[]. n är storleken på högfunktionen heapify(arr, N, i) { var största = i; // Initiera störst som rot var l = 2 * i + 1; // vänster = 2*i + 1 var r = 2 *i + 2; // höger = 2*i + 2 // Om vänster barn är större än roten om (l< N && arr[l]>arr[störst]) störst = l; // Om det högra barnet är större än det största hittills om (r< N && arr[r]>arr[största]) största = r; // Om störst inte är rot if (störst != i) { var swap = arr[i]; arr[i] = arr[störst]; arr[största] = byta; // Heapify rekursivt det påverkade underträdet heapify(arr, N, störst); } } /* En verktygsfunktion för att skriva ut array med storlek n */ function printArray(arr) { var N = arr.length; för (var i = 0; i< N; ++i) document.write(arr[i] + ' '); } var arr = [12, 11, 13, 5, 6, 7]; var N = arr.length; sort(arr); document.write( 'Sorted array is'); printArray(arr, N); // This code is contributed by SoumikMondal> PHP // Php program for implementation of Heap Sort // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(&$arr, $N, $i) { $largest = $i; // Initialize largest as root $l = 2*$i + 1; // left = 2*i + 1 $r = 2*$i + 2; // right = 2*i + 2 // If left child is larger than root if ($l < $N && $arr[$l]>$arr[$störst]) $störst = $l; // Om det högra barnet är större än det största hittills om ($r< $N && $arr[$r]>$arr[$largest]) $largest = $r; // Om störst inte är root if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$störst]; $arr[$största] = $swap; // Rekursivt heapify det påverkade underträdet heapify($arr, $N, $störst); } } // huvudfunktion för att göra heap-sorteringsfunktion heapSort(&$arr, $N) { // Bygg heap (ordna om array) för ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // En efter en extrahera ett element från heap för ($i = $N-1; $i> 0; $i--) { // Flytta nuvarande rot till slutet $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // ring max heapify på den reducerade heapen heapify($arr, $i, 0); } } /* En verktygsfunktion för att skriva ut array med storlek n */ function printArray(&$arr, $N) { for ($i = 0; $i< $N; ++$i) echo ($arr[$i].' ') ; } // Driver's program $arr = array(12, 11, 13, 5, 6, 7); $N = sizeof($arr)/sizeof($arr[0]); // Function call heapSort($arr, $N); echo 'Sorted array is ' . '
'; printArray($arr , $N); // This code is contributed by Shivi_Aggarwal ?>> Python3 # Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def heapify(arr, N, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < N and arr[largest] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < N and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, N, largest) # The main function to sort an array of given size def heapSort(arr): N = len(arr) # Build a maxheap. for i in range(N//2 - 1, -1, -1): heapify(arr, N, i) # One by one extract elements for i in range(N-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0) # Driver's code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] # Function call heapSort(arr) N = len(arr) print('Sorted array is') for i in range(N): print('%d' % arr[i], end=' ') # This code is contributed by Mohit Kumra> Produktion
Sorted array is 5 6 7 11 12 13>
Komplexitetsanalys av Hög sortering
Tidskomplexitet: O(N log N)
Hjälputrymme: O(log n), på grund av den rekursiva anropsstacken. Däremot kan hjälputrymme vara O(1) för iterativ implementering.
Viktiga punkter om Heap Sort:
- Högsortering är en algoritm på plats.
- Dess typiska implementering är inte stabil men kan göras stabil (se detta )
- Typiskt 2-3 gånger långsammare än välimplementerat QuickSort . Orsaken till långsamheten är bristen på referenslokal.
Fördelar med Heap Sort:
- Effektiv tidskomplexitet: Heap Sort har en tidskomplexitet på O(n log n) i alla fall. Detta gör det effektivt för att sortera stora datamängder. De log n faktorn kommer från höjden på den binära högen, och den säkerställer att algoritmen bibehåller god prestanda även med ett stort antal element.
- Minnesanvändning - Minnesanvändningen kan vara minimal (genom att skriva en iterativ heapify() istället för en rekursiv). Så bortsett från vad som är nödvändigt för att hålla den första listan över objekt som ska sorteras, behöver det inget extra minnesutrymme för att fungera
- Enkelhet – Den är enklare att förstå än andra lika effektiva sorteringsalgoritmer eftersom den inte använder avancerade datavetenskapliga begrepp som rekursion.
Nackdelar med Heap Sort:
- Kostsam : Högsortering är kostsamt eftersom konstanterna är högre jämfört med merge sortering även om tidskomplexiteten är O(n Log n) för båda.
- Instabil : Högsorteringen är instabil. Det kan omorganisera den relativa ordningen.
- Effektiv: Heap Sort är inte särskilt effektivt när man arbetar med mycket komplexa data.
Vanliga frågor relaterade till Heap Sort
Q1. Vilka är de två faserna av Heap Sort?
Högsorteringsalgoritmen består av två faser. I den första fasen omvandlas arrayen till en maxhög. Och i den andra fasen tas det högsta elementet bort (d.v.s. det vid trädroten) och de återstående elementen används för att skapa en ny maxhög.
Q2. Varför är Heap Sort inte stabil?
Högsorteringsalgoritmen är inte en stabil algoritm eftersom vi byter arr[i] med arr[0] i heapSort() vilket kan ändra den relativa ordningen för motsvarande nycklar.
Q3. Är Heap Sort ett exempel på Divide and Conquer-algoritmen?
Hög sort är INTE alls en Divide and Conquer-algoritm. Den använder en högdatastruktur för att effektivt sortera dess element och inte en dela och erövra metod för att sortera elementen.
Q4. Vilken sorteringsalgoritm är bättre – Högsortering eller Merge Sort?
Svaret ligger i jämförelsen av deras tidskomplexitet och utrymmesbehov. Merge-sorteringen är något snabbare än Heap-sorteringen. Men å andra sidan tar merge sort extra minne. Beroende på kravet bör man välja vilken man ska använda.
F5. Varför är högsortering bättre än urvalssortering?
Högsortering liknar urvalssortering, men med ett bättre sätt att få det maximala elementet. Den drar fördel av högdatastrukturen för att få det maximala elementet i konstant tid