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:

Heap Sort Algoritme

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æ.

Opret bunkesortering med eksempel

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.

Opret bunkesortering med eksempel

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.

Opret bunkesortering med eksempel

Opret bunkesortering med eksempel

Trin 3) Node 60 og 4 har overordnet node 5. Da "5" er mindre end den underordnede node 60, vil den blive byttet.

Opret bunkesortering med eksempel

Opret bunkesortering med eksempel

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.

Opret bunkesortering med eksempel

Trin 5) Node 10 vil blive byttet med 60 og derefter byttet med 17. Processen vil se ud som følgende.

Opret bunkesortering med eksempel

Opret bunkesortering med eksempel

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.

Opret bunkesortering med eksempel

Opret bunkesortering med eksempel

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.

Opret bunkesortering med eksempel

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.

Min Heap og Max Heap
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:

Tilføjelse af en ny node og Heapify
Tilføjelse af en ny node og heapify

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:

Array-baseret repræsentation af Max Heap
Array-baseret repræsentation af den maksimale heap

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:

  1. Bedste Sag
  2. Gennemsnitlig sag
  3. 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.

Tid og rum kompleksitetsanalyse

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).