Halomrendezési algoritmus (kóddal Python és a C++)

Mi az a kupacrendezési algoritmus?

A Heap Sort az egyik legnépszerűbb és gyorsabb rendezési algoritmus. A teljes bináris fa adatszerkezetre épül. Megkeressük a maximális elemet, és feltesszük a tetejére a max kupachoz. A bináris fa szülőcsomópontjára helyezzük.

Tegyük fel, hogy adott egy tömb, adatok = [10,5].

A tömbben, ha az i-edik (i=0,1,2,3 …) index szülőcsomópont, akkor (2i+1) és (2i+2) lesz a bal és a jobb oldali gyermek. Egy teljes bináris fa létrehozása ezzel a tömbbel így fog kinézni:

A heapify folyamatot a tömb elejétől a végéig végezzük el. Kezdetben, ha a tömböt fává alakítjuk, az a fentihez hasonlóan fog kinézni. Láthatjuk, hogy nem tart fenn semmilyen kupac tulajdonságot (min-heap vagy max heap). A rendezett tömböt úgy kapjuk meg, hogy az összes csomópontnál végrehajtjuk a heapify folyamatot.

A Heap rendezés alkalmazása

Íme a kupacrendezési algoritmus néhány felhasználási módja:

A „Priority Queues” felépítéséhez halomrendezésre van szükség. Mivel a heapsort minden egyes beillesztés után rendezve tartja az elemeket.
A kupac adatstruktúra hatékonyan keresi a k^th a legnagyobb elem egy adott tömbben.
A Linux Kernel a kupac rendezést használja alapértelmezettként rendezési algoritmus mivel O (1) térkomplexitású.

Hozzon létre kupacrendezést a példával

Itt készítünk egy max kupacot a következő teljes bináris fából.

A levél csomópontjai 17, 60, 4, 11 és 45. Nincsenek alárendelt csomópontjaik. Ezért levél csomópontok. Tehát a heapify metódust a szülőcsomópontjukból indítjuk. Íme a lépések:

Step 1) Válassza ki a bal szélső részfát. Ha a gyermek csomópontok nagyobbak, cserélje fel a szülőcsomópontot a gyermek csomóponttal.

Itt a szülőcsomópont a 9. A gyermekcsomópontok pedig a 17 és a 60. Mivel a 60 a legnagyobb, a 60 és 9 felcserélődik, hogy fenntartsák a max halom.

Step 2) Most a bal szélső részfa halmozva van. A következő szülőcsomópont a 7. Ennek a szülőnek két gyermekcsomópontja van, a legnagyobb pedig 45. Tehát a 45 és a 7 felcserélődik.

Step 3) A 60-as és 4-es csomópontnak az 5-ös szülőcsomópontja van. Mivel az „5” kisebb, mint a 60-as gyermekcsomópont, felcserélődik.

Step 4) Most az 5. csomópont rendelkezik a 17,9 gyermekcsomóponttal. Ez nem tartja fenn a max kupac tulajdonságot. Tehát az 5 helyett 17 lesz.

Step 5) A 10-es csomópont felcserélődik 60-ra, majd 17-re. A folyamat a következőképpen fog kinézni.

Step 6) Az 5. lépésig létrehoztuk a maximális kupacot. Minden szülőcsomópont nagyobb, mint a gyermekcsomópontjai. A gyökércsomópont maximális értéke (60).

Jegyzet: A rendezett tömb létrehozásához le kell cserélnünk a max értékű csomópontot az utódjára.

Ezt a folyamatot "kivonat max”. Mivel a 60 a maximális csomópont, a pozícióját a 0. indexhez rögzítjük, és létrehozzuk a kupacot a 60-as csomópont nélkül.

Step 7) Ha a 60-at eltávolítjuk, a következő maximális érték 45. A 45-ös csomópontból ismét elvégezzük a „Max kivonás” műveletet.

Ezúttal 45-öt kapunk, és lecseréljük a gyökércsomópontot az utódjára, a 17-re.

teljesítenünk kell"Kivonat max”-ig, amíg az összes elem nincs rendezve.

Miután elvégeztük ezeket a lépéseket, amíg ki nem bontjuk az összes max értéket, a következő tömböt kapjuk.

Mi az a bináris kupac?

A bináris kupac egyfajta teljes bináris fa adatszerkezet. Az ilyen típusú fastruktúrákban a szülőcsomópont nagyobb vagy kisebb, mint a gyermek csomópontok. Ha a szülőcsomópont kisebb, akkor a kupacot „Minimális kupacnak”, és ha a szülőcsomópont nagyobb, a kupacot „Max. kupacnak” nevezik.

Íme példák a minimális kupacra és a maximális kupacra.

A fenti ábrán, ha a „Min Heap”-et észleli, a szülőcsomópont mindig kisebb, mint a gyermek csomópontok. A fa élén a legkisebb 10-es értéket találjuk.

Hasonlóképpen, a „Max Heap” esetében a szülőcsomópont mindig nagyobb, mint a gyermek csomópontok. A maximális elem a „Max Heap” fejcsomópontjában található.

Mi az a „Heapify”?

„Heapify” a kupac elve, amely biztosítja a csomópont helyzetét. A Heapify-ban a maximális kupac mindig kapcsolatot tart fenn a szülővel és a gyermekkel, vagyis a szülőcsomópont nagyobb lesz, mint a gyermekcsomópont.

Például, ha új csomópontot adunk hozzá, át kell alakítanunk a kupacot. Előfordulhat azonban, hogy módosítanunk kell a csomópontokat, vagy át kell rendeznünk a tömböt. A kupac átformálásának ezt a folyamatát „halmozódásnak” nevezik.

Íme egy példa a heapify működésére:

Új csomópont hozzáadása és Heapify — Új csomópont hozzáadása és halmozás

Íme a heapify lépései:

Step 1) A 65. csomópont hozzáadva a 60. csomópont megfelelő gyermekeként.

Step 2) Ellenőrizze, hogy az újonnan hozzáadott csomópont nagyobb-e, mint a szülő.

Step 3) Mivel nagyobb, mint a szülőcsomópont, a megfelelő gyermeket felcseréltük a szülővel.

Hogyan építsük fel a kupacot

A kupac építése vagy a fa felhalmozása előtt tudnunk kell, hogyan fogjuk tárolni. Mivel a kupac egy teljes bináris fa, jobb, ha egy sor a kupac adatainak tárolására.

Tegyük fel, hogy egy tömb összesen n elemet tartalmaz. Ha az „i” index egy szülőcsomópont, akkor a bal oldali csomópont az indexen lesz (2i+1), és a jobb oldali csomópont az indexen lesz (2i+2). Feltételezzük, hogy a tömb indexe 0-tól kezdődik.

Ennek segítségével tároljunk egy max kupacot egy tömbszerű következőben:

A Max Heap tömb alapú ábrázolása — A max kupac tömb alapú ábrázolása

A heapify algoritmus fenntartja a kupac tulajdonságot. Ha a szülő nem rendelkezik a szélső értékkel (kisebb vagy nagyobb), akkor a rendszer a legszélsőségesebb gyermekcsomópontra cseréli.

Íme a lépések a maximális kupac felhalmozásához:

Step 1) Kezdje a levél csomópontjától.

Step 2) Találd meg a maximumot a szülő és a gyerekek között.

Step 3) Cserélje ki a csomópontokat, ha a gyermek csomópont értéke nagyobb, mint a szülőé.

Step 4) Menj egy szinttel feljebb.

Step 5) Kövesse a 2,3,4, 0, XNUMX lépéseket, amíg el nem éri a XNUMX indexet, vagy rendezi a teljes fát.

Íme a rekurzív halomozás pszeudokódja (max. kupac):

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)

Pszeudo kód a kupacrendezéshez

Íme a kupacrendezési algoritmus pszeudokódja:

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)

Példa a kupacrendezési kódra 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

Példa a kupacrendezési kódra 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

A Heap Sort idő és tér komplexitásának elemzése

Létezik az időbonyolultság és a térbonyolultság, amelyeket a kupacrendezéshez elemezhetünk. Az időbonyolítás érdekében a következő eseteket vesszük figyelembe:

Legjobb eset
Átlagos eset
Legrosszabb esetben

A kupac egy teljes bináris fán van megvalósítva. Tehát a bináris fa alsó szintjén a csomópontok maximális száma lesz. Ha az alsó szinten n csomópont van, akkor a fenti szinten n/2 csomópont lesz.

Ebben a példában a 3. szint négy elemet tartalmaz, a 2. szint két elemet, az 1. szint pedig egy elemet tartalmaz. Ha összesen n darab elem van, akkor a magasság vagy a teljes szint a következő lesz Bejelentkezés₂(n). Tehát egyetlen elem beszúrása legfeljebb Log(n) iterációt igényelhet.

Ha a kupacból a maximális értéket akarjuk venni, csak a gyökércsomópontot vesszük. Ezután futtassa újra a heapify-t. Minden halmozódást vesz igénybe Bejelentkezés₂(N) idő. A maximum kivonása O(1) időt vesz igénybe.

A halomrendezési algoritmus legjobb eset-időbeli összetettsége

Amikor az összes elem már rendezve van a tömbben, O(n) időbe telik a kupac felépítése. Mert ha a lista rendezve van, akkor egy elem beszúrása állandó időt vesz igénybe, ami O(1).

Tehát a legjobb esetben O(n) időbe telik egy max-halom vagy min-heap létrehozása.

Átlagos eset-idő komplexitás a kupacrendezési algoritmushoz

Egy cikk beszúrása vagy egy maximális érték kivonása O(log(n)) időbe kerül. Tehát a kupacrendezési algoritmus átlagos esetidő-bonyolultsága a következő O(n log(n)).

A legrosszabb eset bonyolultsága a halomrendezési algoritmushoz

Az átlagos esethez hasonlóan a legrosszabb forgatókönyv esetén n-szeres halmozódást hajthatunk végre. Minden halmozódás O(log(n)) időbe kerül. Tehát a legrosszabb eset lesz az időbonyolítás O(n log(n)).

Helykomplexitás a kupacrendezési algoritmushoz

A halomrendezés egy helyben tervezett algoritmus. Ez azt jelenti, hogy a feladat végrehajtásához nincs szükség extra vagy ideiglenes memóriára. Ha látjuk a megvalósítást, észrevesszük, hogy a swap ()-t használtuk a csomópontok cseréjéhez. Más listára vagy tömbre nem volt szükség. Tehát a tér komplexitása O(1).

Talán tetszene: