Heap Sort Algorithm (Med kode i Python og C++)
Hvad er Heap Sort Algorithm?
Heap Sort er en af de populære og hurtigere sorteringsalgoritmer. Det er bygget på den komplette binære trædatastruktur. Vi vil søge efter det maksimale element og lægge det øverst for den maksimale bunke. Vi vil sætte det på forældreknudepunktet for det binære træ.
Lad os sige, at der er givet en matrix, data = [10,5, 7, 9, 4, 11, 45, 17, 60].
I arrayet, hvis i-th (i=0,1,2,3 …) indeks er en overordnet node, vil (2i+1) og (2i+2) være venstre og højre børn. Oprettelse af et komplet binært træ med dette array vil se sådan ud:
Vi vil udføre heapify-processen fra begyndelsen til slutningen af arrayet. I første omgang, hvis vi konverterer arrayet til et træ, vil det se ud som ovenstående. Vi kan se, at det ikke opretholder nogen heap-egenskab (min-heap eller max heap). Vi får det sorterede array ved at udføre heapify-processen for alle noderne.
Anvendelse af Heap Sort
Her er lidt brug af heap-sorteringsalgoritmen:
- Konstruktion af "Prioritetskøer" har brug for bunke sortering. Fordi heapsort holder elementet sorteret efter hver indsættelse.
- Heap Data Structure er effektiv til at finde kth største element i en given matrix.
- Linux Kernel bruger heap-sorteringen som standard sorteringsalgoritme da det har O (1) rumkompleksitet.
Opret bunkesortering med eksempel
Her vil vi konstruere en max bunke fra følgende komplette binære træ.
Bladknuderne er 17, 60, 4, 11 og 45. De har ingen børneknuder. Det er derfor, de er bladknuder. Så vi starter heapify-metoden fra deres overordnede node. Her er trinene:
Trin 1) Vælg undertræet længst til venstre. Hvis de underordnede knudepunkter er større, skal du udskifte den overordnede knude med den underordnede knude.
Her er den overordnede node 9. Og de underordnede noder er 17 og 60. Da 60 er den største, vil 60 og 9 blive byttet for at bevare max bunke.
Trin 2) Nu er undertræet længst til venstre ophobet. Den næste overordnede node er 7. Denne forælder har to underordnede noder, og den største er 45. Så 45 og 7 vil blive byttet om.
Trin 3) Node 60 og 4 har overordnet node 5. Da "5" er mindre end den underordnede node 60, vil den blive byttet.
Trin 4) Nu har node 5 den underordnede node 17,9. Dette opretholder ikke egenskaben for max heap. Så 5 vil blive erstattet med 17.
Trin 5) Node 10 vil blive byttet med 60 og derefter byttet med 17. Processen vil se ud som følgende.
Trin 6) Op til trin 5 oprettede vi den maksimale heap. Hver overordnet node er større end dens underordnede noder. Rodnoden har den maksimale værdi (60).
Bemærk: For at oprette det sorterede array skal vi erstatte noden med maksimal værdi med dens efterfølger.
Denne proces kaldes "udtræk max”. Da 60 er den maksimale node, vil vi fiksere dens position til det 0. indeks og oprette heapen uden node 60.
Trin 7) Da 60 er fjernet, så er den næste maksimale værdi 45. Vi vil gøre processen "Extract Max" igen fra node 45.
Denne gang får vi 45 og erstatter rodnoden med dens efterfølger 17.
Vi skal præstere"Udtræk Max” indtil alle elementer er sorteret.
Efter at have udført disse trin, indtil vi udtrækker alle de maksimale værdier, får vi følgende array.
Hvad er Binary Heap?
En binær bunke er en slags komplet binært træ datastruktur. I denne slags træstruktur er den overordnede node enten større eller mindre end de underordnede noder. Hvis forældreknuden er mindre, kaldes heapen "Min Heap", og hvis forældreknuden er større, kaldes heapen "Max Heap".
Her er eksempler på min heap og max heap.
I ovenstående figur, hvis du bemærker "Min Heap", er den overordnede node altid mindre end dens underordnede noder. I toppen af træet kan vi finde den mindste værdi 10.
Tilsvarende for "Max Heap" er den overordnede node altid større end de underordnede noder. Det maksimale element er til stede ved hovedknuden for "Max Heap".
Hvad er "Heapify"?
"Heapify" er princippet for heapen, der sikrer nodens position. I Heapify opretholder en max heap altid et forhold til forælder og barn, og det vil sige, at forældreknudepunktet vil være større end underknudepunkterne.
For eksempel, hvis en ny node tilføjes, skal vi omforme heapen. Vi skal dog muligvis ændre eller udskifte noderne eller omarrangere array. Denne proces med at omforme en heap kaldes "heapify".
Her er et eksempel på, hvordan heapify virker:
Her er trinene til heapify:
Trin 1) Tilføjet node 65 som det rigtige underordnede af node 60.
Trin 2) Tjek, om den nyligt tilføjede node er større end den overordnede.
Trin 3) Da den er større end forældreknuden, byttede vi det rigtige barn ud med dets forælder.
Hvordan man bygger dyngen
Før vi bygger dyngen eller ophober et træ, skal vi vide, hvordan vi opbevarer det. Da dyngen er et komplet binært træ, er det bedre at bruge en matrix til at opbevare dataene i dyngen.
Lad os sige, at et array indeholder i alt n elementer. Hvis "i" indeks er en overordnet node, så vil venstre node være ved indeks (2i+1), og den højre knude vil være ved indeks (2i+2). Vi antager, at array-indekset begynder fra 0.
Ved at bruge dette, lad os gemme en maksimal bunke til et array-lignende følgende:
Heapify-algoritmen vedligeholder heap-egenskaben. Hvis forælderen ikke har den ekstreme værdi (mindre eller større), vil den blive byttet med den mest ekstreme underordnede node.
Her er trinene til at heapify en max heap:
Trin 1) Start fra bladknuden.
Trin 2) Find maksimum mellem forældre og børn.
Trin 3) Skift noderne, hvis den underordnede node har en større værdi end den overordnede.
Trin 4) Gå et niveau op.
Trin 5) Følg trin 2,3,4 indtil vi når indeks 0 eller sorter hele træet.
Her er pseudokoden for rekursiv heapify (max heap):
def heapify(): input→ array, size, i largest = i left = 2*i + 1 right = 2*i + 2 if left<n and array[largest ] < array[left]: largest = left if right<n and array[largest ] < array[right]: largest = right If largest not equals i: swap(array[i],array[largest]) heapify(array,n,largest)
Pseudokode for heapsortering
Her er pseudokoden for heap-sorteringsalgoritmen:
Heapify(numbers as an array, n as integer, i as integer): largest = i left = 2i+1 right= 2i+2 if(left<=n) and (numbers[i]<numbers[left]) largest=left if(right<=n) and (numbers[i]<numbers[right]) largest=right if(largest != i) swap(numbers[i], numbers[largest]) Heapify(numbers,n,largest) HeapSort(numbers as an array): n= numbers.size() for i in range n/2 to 1 Heapify(numbers,n,i) for i in range n to 2 Swap numbers[i] with numbers[1] Heapify(numbers,i,0)
Eksempel på heap-sorteringskode i C++
#include <iostream> using namespace std; void display(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << "\t"; } cout << endl; } void heapify(int numbers[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && numbers[left] < numbers[largest]) { largest = left; } if (right < n && numbers[right] < numbers[largest]) { largest = right; } if (largest != i) { //uncomment the following line to see details in output //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl; swap(numbers[i], numbers[largest]); heapify(numbers, n, largest); } } void heapSort(int numbers[], int n) { for (int i = n/2 - 1; i >= 0; i--) { heapify(numbers, n, i); //uncomment the following line to see details in output //cout<<"Heapify:\t"; //display(numbers,n); } for (int i = n - 1; i >= 0; i--) { swap(numbers[0], numbers[i]); heapify(numbers, i, 0); } } int main() { int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60}; int size = sizeof(numbers) / sizeof(numbers[0]); cout<<"Initial Array:\t"; display(numbers,size); heapSort(numbers, size); cout<<"Sorted Array (descending order):\t"; display(numbers, size); }
Output:
Initial Array: 10 5 7 9 4 11 45 17 60 Sorted Array (descending order): 60 45 17 11 10 9 7 5 4
Eksempel på heap-sorteringskode i Python
def display(arr): for i in range(len(arr)): print(arr[i], end = "\t") print() def heapify(numbers, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and numbers[left] < numbers[largest]: largest = left if right < n and numbers[right] < numbers[largest]: largest = right if largest != i: numbers[i], numbers[largest] = numbers[largest], numbers[i] heapify(numbers, n, largest) def heapSort(items, n): for i in range(n //2,-1,-1): heapify(items, n, i) for i in range(n - 1, -1, -1): items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)
Output:
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
Tid og rum kompleksitetsanalyse af Heap Sort
Der er tidskompleksitet og rumkompleksitet, som vi kan analysere for bunken. For tidskompleksitet har vi følgende cases:
- Bedste Sag
- Gennemsnitlig sag
- Værste tilfælde
Heapen er implementeret på et komplet binært træ. Så på det nederste niveau af det binære træ vil der være det maksimale antal noder. Hvis det nederste niveau har n noder, vil ovenstående niveau have n/2 noder.
I dette eksempel har niveau 3 fire elementer, niveau 2 har to elementer, og niveau 1 har et element. Hvis der er et totalt n antal elementer, vil højden eller det samlede niveau være Log2(n). Så indsættelse af et enkelt element kunne tage maksimalt Log(n) iterationer.
Når vi vil tage den maksimale værdi fra heapen, tager vi bare rodknuden. Så igen, kør heapify. Hver heapify tager Log2(N) tid. Udtræk af maksimum tager O(1) tid.
Bedste Case Time Complexity for Heap Sort Algorithm
Når alle elementer allerede er sorteret i arrayet, vil det tage O(n) tid at bygge heapen. Fordi hvis listen er sorteret, vil indsættelse af et element tage den konstante tid, der er O(1).
Så det vil tage O(n) tid at skabe en max-heap eller min-heap i bedste fald.
Gennemsnitlig sagstidskompleksitet for heapsorteringsalgoritme
Indsættelse af en vare eller udtrækning af et maksimum koster O(log(n)) tid. Så den gennemsnitlige sagstidskompleksitet for heap-sorteringsalgoritmen er O(n log(n)).
Worst Case Tidskompleksitet for Heap Sort Algorithm
I lighed med det gennemsnitlige tilfælde kan vi i værste tilfælde udføre heapify n gange. Hver heapify vil koste O(log(n)) tid. Så den værste tidskompleksitet vil være O(n log(n)).
Rumkompleksitet for heapsorteringalgoritme
Heap sort er en in-place designet algoritme. Det betyder, at der ikke er behov for ekstra eller midlertidig hukommelse for at udføre opgaven. Hvis vi ser implementeringen, vil vi bemærke, at vi brugte swap () til at udføre udvekslingen af noderne. Ingen anden liste eller array var nødvendig. Så rumkompleksiteten er O(1).