Algoritmus řazení haldy (s vloženým kódem Python si C++)
Sarah Chen
Co je algoritmus řazení haldy?
Heap Sort je jedním z populárních a rychlejších třídicích algoritmů. Je postaven na kompletní binární stromové datové struktuře. Vyhledáme maximální prvek a dáme ho nahoru pro maximální hromadu. Umístíme jej na nadřazený uzel binárního stromu.
Řekněme, že je dáno pole, data = [10,5, 7, 9, 4, 11, 45, 17, 60].
Pokud je v poli i-tý (i=0,1,2,3 …) index nadřazeným uzlem, pak (2i+1) a (2i+2) budou levé a pravé potomky. Vytvoření kompletního binárního stromu s tímto polem bude vypadat takto:
Provedeme proces heapify od začátku do konce pole. Zpočátku, pokud pole převedeme na strom, bude vypadat jako výše. Vidíme, že neudržuje žádnou vlastnost haldy (min-heap nebo max halda). Seřazené pole získáme provedením procesu heapify pro všechny uzly.
Aplikace Heap Sort
Zde je nějaké použití algoritmu řazení haldy:
- Konstrukce „Prioritních front“ vyžaduje třídění haldy. Protože heapsort udržuje prvek seřazený po každém vložení.
- Struktura dat haldy je efektivní při hledání kth největší prvek v daném poli.
- Linuxové jádro používá řazení haldy jako výchozí algoritmus třídění protože má O (1) prostorovou složitost.
Vytvořte řazení haldy s příkladem
Zde vytvoříme maximální haldu z následujícího kompletního binárního stromu.
Listové uzly jsou 17, 60, 4, 11 a 45. Nemají žádné podřízené uzly. Proto jsou to listové uzly. Spustíme tedy metodu heapify z jejich nadřazeného uzlu. Zde jsou kroky:
Krok 1) Vyberte podstrom nejvíce vlevo. Pokud jsou podřízené uzly větší, zaměňte nadřazený uzel za podřízený uzel.
Zde je nadřazený uzel 9. A podřízené uzly jsou 17 a 60. Protože 60 je největší, 60 a 9 budou prohozeny, aby se zachoval max hromada.
Krok 2) Nyní je podstrom nejvíce vlevo nahromaděný. Další nadřazený uzel je 7. Tento nadřazený uzel má dva podřízené uzly a největší je 45. Takže 45 a 7 budou prohozeny.
Krok 3) Uzly 60 a 4 mají nadřazený uzel 5. Protože „5“ je menší než podřízený uzel 60, bude prohozen.
Krok 4) Nyní má uzel 5 podřízený uzel 17,9. Toto nezachovává vlastnost maximální haldy. Takže 5 bude nahrazeno 17.
Krok 5) Uzel 10 bude prohozen s 60 a poté s 17. Proces bude vypadat následovně.
Krok 6) Až do kroku 5 jsme vytvořili maximální haldu. Každý nadřazený uzel je větší než jeho podřízené uzly. Kořenový uzel má maximální hodnotu (60).
Poznámka: Abychom vytvořili seřazené pole, musíme nahradit uzel s maximální hodnotou jeho následníkem.
Tento proces se nazývá „extrahovat max“. Protože 60 je maximální uzel, zafixujeme jeho pozici na 0. index a vytvoříme haldu bez uzlu 60.
Krok 7) Po odstranění 60 je další maximální hodnota 45. Z uzlu 45 znovu provedeme proces „Extrahovat Max“.
Tentokrát dostaneme 45 a nahradíme kořenový uzel jeho nástupcem 17.
Musíme předvést"Extrakt Max“, dokud nebudou všechny prvky seřazeny.
Po provedení těchto kroků, dokud extrahujeme všechny maximální hodnoty, získáme následující pole.
Co je binární halda?
Binární halda je druh kompletní binární strom datová struktura. V tomto druhu stromové struktury je nadřazený uzel větší nebo menší než podřízené uzly. Pokud je nadřazený uzel menší, pak se halda nazývá „Min Heap“ a pokud je nadřazený uzel větší, halda se nazývá „Max Halda“.
Zde jsou příklady minimální haldy a maximální haldy.
Pokud si na výše uvedeném obrázku všimnete „Min Heap“, nadřazený uzel je vždy menší než jeho podřízené uzly. V čele stromu najdeme nejmenší hodnotu 10.
Podobně pro „Max Heap“ je nadřazený uzel vždy větší než podřízené uzly. Maximální prvek je přítomen v hlavním uzlu pro „Max Heap“.
Co je to „Heapify“?
„Heapify“ je princip haldy, který zajišťuje polohu uzlu. V Heapify maximální hromada vždy udržuje vztah s nadřazeným a podřízeným uzlem, což znamená, že nadřazený uzel bude větší než podřízené uzly.
Pokud je například přidán nový uzel, musíme haldu přetvořit. Možná však budeme muset změnit nebo vyměnit uzly nebo změnit uspořádání pole. Tento proces přetváření hromady se nazývá „heapify“.
Zde je příklad toho, jak heapify funguje:
Zde jsou kroky pro heapify:
Krok 1) Přidán uzel 65 jako správný potomek uzlu 60.
Krok 2) Zkontrolujte, zda je nově přidaný uzel větší než nadřazený uzel.
Krok 3) Protože je větší než nadřazený uzel, vyměnili jsme správného potomka s jeho rodičem.
Jak postavit haldu
Před stavbou haldy nebo navršením stromu musíme vědět, jak jej budeme skladovat. Protože halda je úplný binární strom, je lepší použít an řada uchovávat data haldy.
Řekněme, že pole obsahuje celkem n prvků. Pokud je „i“ index nadřazeným uzlem, bude levý uzel na indexu (2i+1)a pravý uzel bude v indexu (2i+2). Předpokládáme, že index pole začíná od 0.
Pomocí toho uložme maximální hromadu do následujícího pole:
Algoritmus heapify udržuje vlastnost haldy. Pokud rodič nemá extrémní hodnotu (menší nebo větší), bude prohozen s nejextrémnějším podřízeným uzlem.
Zde jsou kroky k nahromadění maximální hromady:
Krok 1) Začněte od listového uzlu.
Krok 2) Najděte maximum mezi rodičem a dětmi.
Krok 3) Prohoďte uzly, pokud má podřízený uzel větší hodnotu než nadřazený uzel.
Krok 4) Jděte o úroveň výš.
Krok 5) Postupujte podle kroků 2,3,4, 0, XNUMX, dokud nedosáhneme indexu XNUMX nebo seřadíme celý strom.
Zde je pseudokód pro rekurzivní heapify (maximální halda):
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)
Pseudo kód pro třídění haldy
Zde je pseudokód pro algoritmus řazení haldy:
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říklad kódu řazení haldy v 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);
}
Výstup:
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říklad kódu řazení haldy v 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)
Výstup:
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
Analýza časové a prostorové složitosti Heap Sort
Existuje časová složitost a prostorová složitost, které můžeme analyzovat pro řazení haldy. Pro časovou složitost máme následující případy:
- Nejlepší případ
- Průměrný případ
- Nejhorší případ
Halda je implementována na kompletním binárním stromu. Takže na spodní úrovni binárního stromu bude maximální počet uzlů. Pokud má spodní úroveň n uzlů, pak výše uvedená úroveň bude mít n/2 uzlů.
V tomto příkladu má úroveň 3 čtyři předměty, úroveň 2 dvě věci a úroveň 1 jednu věc. Pokud je celkem n položek, bude výška nebo celková úroveň Log2(n). Takže vložení jednoho prvku může trvat maximálně iterací Log(n).
Když chceme vzít maximální hodnotu z haldy, vezmeme pouze kořenový uzel. Poté znovu spusťte heapify. Každé heapify zabere Log2(n) čas. Extrakce maxima trvá O(1) čas.
Nejlepší případová časová složitost pro algoritmus řazení haldy
Když jsou všechny prvky již v poli seřazeny, bude vytvoření haldy trvat O(n) času. Protože pokud je seznam seřazený, pak vložení položky zabere konstantní čas, který je O(1).
Takže vytvoření maximální nebo minimální haldy v nejlepším případě zabere O(n) čas.
Průměrná časová složitost pro algoritmus řazení haldy
Vložení položky nebo vyjmutí maximálního nákladu O(log(n)) čas. Průměrná časová složitost případu pro algoritmus řazení haldy je tedy O(n log(n)).
Nejhorší případ časové složitosti pro algoritmus řazení haldy
Podobně jako v průměrném případě bychom v nejhorším scénáři mohli provést heapify nkrát. Každé heapify bude stát O(log(n)) času. Časová složitost tedy bude v nejhorším případě O(n log(n)).
Prostorová složitost pro algoritmus řazení haldy
Řazení haldy je algoritmus navržený na místě. To znamená, že k provedení úkolu není potřeba žádná další nebo dočasná paměť. Pokud vidíme implementaci, všimneme si, že jsme použili swap () k provedení výměny uzlů. Nebyl potřeba žádný další seznam nebo pole. Prostorová složitost je tedy O(1).
