U ovom ćemo članku raspravljati o Heapsort algoritmu. Heap sortiranje obrađuje elemente stvaranjem min-heap ili max-heap koristeći elemente zadanog niza. Min-heap ili max-heap predstavlja poredak niza u kojem korijenski element predstavlja minimalni ili maksimalni element niza.

Sortiranje gomile u osnovi rekurzivno izvodi dvije glavne operacije -

• Izgradite gomilu H koristeći elemente niza.
• Više puta izbrišite korijenski element gomile formirane u 1^svfaza.

Prije nego saznamo više o heap sortiranju, prvo pogledajmo kratak opis Hrpa.

Što je gomila?

Hrpa je potpuno binarno stablo, a binarno stablo je stablo u kojem čvor može imati najviše dva djeteta. Potpuno binarno stablo je binarno stablo u kojem sve razine osim zadnje razine, tj. lisnog čvora, trebaju biti u potpunosti popunjene, a svi čvorovi trebaju biti poravnati lijevo.

Što je heap sortiranje?

Heapsort je popularan i učinkovit algoritam sortiranja. Koncept heap sortiranja je eliminirati elemente jedan po jedan iz heap dijela liste, a zatim ih umetnuti u sortirani dio liste.

Heapsort je algoritam za sortiranje na mjestu.

np.jedinstven

Sada, da vidimo algoritam heap sortiranja.

Algoritam

 HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End 

BuildMaxHeap(arr)

 BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End 

MaxHeapify(arr,i)

 MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End 

Rad algoritma Heap sortiranja

Sada, da vidimo kako radi Heapsort algoritam.

Kod heap sortiranja, u osnovi, postoje dvije faze uključene u sortiranje elemenata. Korištenjem algoritma za sortiranje gomile, oni su sljedeći -

• Prvi korak uključuje stvaranje heapa podešavanjem elemenata niza.
• Nakon stvaranja gomile, sada nekoliko puta uklonite korijenski element gomile pomicanjem na kraj niza, a zatim pohranite strukturu gomile s preostalim elementima.

Pogledajmo sada detaljno funkcioniranje heap sortiranja pomoću primjera. Da bismo to jasnije razumjeli, uzmimo nesortirani niz i pokušajmo ga sortirati korištenjem heap sortiranja. To će objašnjenje učiniti jasnijim i lakšim.

Prvo, moramo konstruirati hrpu iz zadanog niza i pretvoriti je u maksimalnu hrpu.

Nakon pretvaranja zadane gomile u najveću gomilu, elementi niza su -

Zatim moramo izbrisati korijenski element (89) iz maksimalne hrpe. Da bismo izbrisali ovaj čvor, moramo ga zamijeniti s posljednjim čvorom, tj. (jedanaest). Nakon brisanja root elementa, ponovno ga moramo heapificirati da bismo ga pretvorili u max heap.

Nakon izmjene elementa niza 89 s jedanaest, i pretvarajući hrpu u maksimalnu hrpu, elementi niza su -

U sljedećem koraku, opet, moramo izbrisati root element (81) iz maksimalne hrpe. Da bismo izbrisali ovaj čvor, moramo ga zamijeniti s posljednjim čvorom, tj. (54). Nakon brisanja korijenskog elementa, ponovno ga moramo heapificirati da bismo ga pretvorili u maksimalnu hrpu.

Nakon izmjene elementa niza 81 s 54 i pretvarajući hrpu u maksimalnu hrpu, elementi niza su -

U sljedećem koraku moramo izbrisati root element (76) opet iz maksimalne hrpe. Da bismo izbrisali ovaj čvor, moramo ga zamijeniti s posljednjim čvorom, tj. (9). Nakon brisanja korijenskog elementa, ponovno ga moramo heapificirati da bismo ga pretvorili u maksimalnu hrpu.

Nakon izmjene elementa niza 76 s 9 i pretvarajući hrpu u maksimalnu hrpu, elementi niza su -

U sljedećem koraku opet moramo izbrisati root element (54) iz maksimalne hrpe. Da bismo izbrisali ovaj čvor, moramo ga zamijeniti s posljednjim čvorom, tj. (14). Nakon brisanja korijenskog elementa, ponovno ga moramo heapificirati da bismo ga pretvorili u maksimalnu hrpu.

Nakon izmjene elementa niza 54 s 14 i pretvarajući hrpu u maksimalnu hrpu, elementi niza su -

U sljedećem koraku opet moramo izbrisati root element (22) iz maksimalne hrpe. Da bismo izbrisali ovaj čvor, moramo ga zamijeniti s posljednjim čvorom, tj. (jedanaest). Nakon brisanja korijenskog elementa, ponovno ga moramo heapificirati da bismo ga pretvorili u maksimalnu hrpu.

Nakon izmjene elementa niza 22 s jedanaest i pretvarajući hrpu u maksimalnu hrpu, elementi niza su -

xor cpp

U sljedećem koraku opet moramo izbrisati root element (14) iz maksimalne hrpe. Da bismo izbrisali ovaj čvor, moramo ga zamijeniti s posljednjim čvorom, tj. (9). Nakon brisanja korijenskog elementa, ponovno ga moramo heapificirati da bismo ga pretvorili u maksimalnu hrpu.

Nakon izmjene elementa niza 14 s 9 i pretvarajući hrpu u maksimalnu hrpu, elementi niza su -

U sljedećem koraku opet moramo izbrisati root element (jedanaest) iz maksimalne hrpe. Da bismo izbrisali ovaj čvor, moramo ga zamijeniti s posljednjim čvorom, tj. (9). Nakon brisanja root elementa, ponovno ga moramo heapificirati da bismo ga pretvorili u max heap.

Nakon izmjene elementa niza jedanaest s 9, elementi niza su -

Sada hrpi ostaje samo jedan element. Nakon brisanja hrpa će biti prazna.

Nakon završetka sortiranja, elementi niza su -

Sada je niz potpuno sortiran.

Složenost sortiranja gomile

Sada, da vidimo vremensku složenost Heap sortiranja u najboljem slučaju, prosječnom slučaju i najgorem slučaju. Također ćemo vidjeti kompleksnost prostora Heapsorta.

1. Vremenska složenost

Složenost u najboljem slučaju -To se događa kada nije potrebno sortiranje, tj. niz je već sortiran. Najbolja vremenska složenost heap sortiranja je O(n log). Prosječna složenost slučaja -To se događa kada su elementi niza u zbrkanom redoslijedu koji nije ispravno uzlazan i nije ispravno silazni. Prosječna složenost slučaja razvrstavanja hrpe je O(n log n). Složenost u najgorem slučaju -To se događa kada se elementi niza moraju sortirati obrnutim redoslijedom. To znači da pretpostavimo da morate sortirati elemente niza uzlaznim redoslijedom, ali njegovi elementi su u silaznom redoslijedu. Vremenska složenost sortiranja hrpe u najgorem slučaju je O(n log n).

Vremenska složenost heap sortiranja je O (n dnevnik) u sva tri slučaja (najbolji slučaj, prosječan slučaj i najgori slučaj). Visina potpunog binarnog stabla koje ima n elemenata je smiriti.

2. Složenost prostora

• Prostorna složenost Heap sortiranja je O(1).

Implementacija Heapsorta

Pogledajmo sada programe Heap sortiranja u različitim programskim jezicima.

Program: Napišite program za implementaciju heap sortiranja u C jeziku.

 #include /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are - 
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>