V tem članku bomo razpravljali o algoritmu Heapsort. Razvrščanje kopice obdela elemente tako, da ustvari najmanjšo kopico ali največjo kopico z uporabo elementov podane matrike. Min-heap ali max-heap predstavlja vrstni red matrike, v kateri korenski element predstavlja najmanjši ali največji element matrike.

Razvrščanje kopice v bistvu rekurzivno izvaja dve glavni operaciji -

• Zgradite kup H z uporabo elementov matrike.
• Večkrat izbrišite korenski element kopice, oblikovane v 1^stfaza.

Preden izvemo več o razvrščanju kopice, si najprej oglejmo kratek opis Kup.

Kaj je kopica?

Kup je popolno binarno drevo, binarno drevo pa je drevo, v katerem ima lahko vozlišče največ dva otroka. Popolno binarno drevo je binarno drevo, v katerem morajo biti vse ravni, razen zadnje ravni, tj.

Kaj je razvrščanje kopice?

Heapsort je priljubljen in učinkovit algoritem za razvrščanje. Koncept kopičnega razvrščanja je odstraniti elemente enega za drugim iz kopičnega dela seznama in jih nato vstaviti v razvrščeni del seznama.

Heapsort je algoritem za razvrščanje na mestu.

css meja

Zdaj pa poglejmo algoritem razvrščanja kopice.

Algoritem

 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 

Delovanje algoritma za razvrščanje kopice

Zdaj pa poglejmo delovanje algoritma Heapsort.

Pri razvrščanju na kup sta v osnovi vključeni dve fazi razvrščanja elementov. Z uporabo algoritma za razvrščanje kopice so naslednji -

• Prvi korak vključuje ustvarjanje kopice s prilagajanjem elementov matrike.
• Po ustvarjanju kopice zdaj večkrat odstranite korenski element kopice, tako da ga premaknete na konec matrike, nato pa shranite strukturo kopice s preostalimi elementi.

Zdaj pa si na primeru podrobno oglejmo delovanje razvrščanja kopice. Da bi to bolj jasno razumeli, vzemimo nerazvrščeno matriko in jo poskusimo razvrstiti z razvrščanjem kopice. Tako bo razlaga jasnejša in lažja.

Najprej moramo sestaviti kopico iz dane matrike in jo pretvoriti v največjo kopico.

Po pretvorbi dane kopice v največjo kopico so elementi polja -

Nato moramo izbrisati korenski element (89) iz največjega kupa. Če želite izbrisati to vozlišče, ga moramo zamenjati z zadnjim vozliščem, tj. (enajst). Ko izbrišemo korenski element, ga moramo znova kopičiti, da ga pretvorimo v največji kup.

Po zamenjavi elementa matrike 89 z enajst, in pretvorbo kopice v max-heap, elementi matrike so -

V naslednjem koraku moramo znova izbrisati korenski element (81) iz največjega kupa. Če želite izbrisati to vozlišče, ga moramo zamenjati z zadnjim vozliščem, tj. (54). Ko izbrišemo korenski element, ga moramo znova kopičiti, da ga pretvorimo v največji kup.

Po zamenjavi elementa matrike 81 z 54 in pretvorbo kopice v max-heap, elementi matrike so -

V naslednjem koraku moramo izbrisati korenski element (76) spet iz največjega kupa. Če želite izbrisati to vozlišče, ga moramo zamenjati z zadnjim vozliščem, tj. (9). Ko izbrišemo korenski element, ga moramo znova kopičiti, da ga pretvorimo v največji kup.

Po zamenjavi elementa matrike 76 z 9 in pretvorbo kopice v max-heap, elementi matrike so -

V naslednjem koraku moramo spet izbrisati korenski element (54) iz največjega kupa. Če želite izbrisati to vozlišče, ga moramo zamenjati z zadnjim vozliščem, tj. (14). Ko izbrišemo korenski element, ga moramo znova kopičiti, da ga pretvorimo v največji kup.

Po zamenjavi elementa matrike 54 z 14 in pretvorbo kopice v max-heap, elementi matrike so -

V naslednjem koraku moramo spet izbrisati korenski element (22) iz največjega kupa. Če želite izbrisati to vozlišče, ga moramo zamenjati z zadnjim vozliščem, tj. (enajst). Ko izbrišemo korenski element, ga moramo znova kopičiti, da ga pretvorimo v največji kup.

Po zamenjavi elementa matrike 22 z enajst in pretvorbo kopice v max-heap, elementi matrike so -

V naslednjem koraku moramo spet izbrisati korenski element (14) iz največjega kupa. Če želite izbrisati to vozlišče, ga moramo zamenjati z zadnjim vozliščem, tj. (9). Ko izbrišemo korenski element, ga moramo znova kopičiti, da ga pretvorimo v največji kup.

Po zamenjavi elementa matrike 14 z 9 in pretvorbo kopice v max-heap, elementi matrike so -

V naslednjem koraku moramo spet izbrisati korenski element (enajst) iz največjega kupa. Če želite izbrisati to vozlišče, ga moramo zamenjati z zadnjim vozliščem, tj. (9). Ko izbrišemo korenski element, ga moramo znova kopičiti, da ga pretvorimo v največji kup.

Po zamenjavi elementa matrike enajst z 9, elementi matrike so -

Sedaj ima kup samo še en element. Ko ga izbrišete, bo kopica prazna.

Po končanem razvrščanju so elementi polja -

Sedaj je niz popolnoma urejen.

Kompleksnost razvrščanja kopice

Zdaj pa poglejmo časovno zapletenost razvrščanja kopice v najboljšem, povprečnem in najslabšem primeru. Videli bomo tudi prostorsko kompleksnost Heapsorta.

cepitev nizov c++

1. Časovna zapletenost

Najboljša zapletenost -Pojavi se, ko razvrščanje ni potrebno, tj. matrika je že razvrščena. Najboljša časovna zapletenost razvrščanja kopice je O (n dnevnik). Povprečna zapletenost primera -Pojavi se, ko so elementi niza v zmešanem vrstnem redu, ki ni pravilno naraščajoče in ni pravilno padajoče. Povprečna časovna zapletenost primera razvrščanja kopice je O(n log n). Kompleksnost v najslabšem primeru -Pojavi se, ko je treba elemente matrike razvrstiti v obratnem vrstnem redu. To pomeni, da morate elemente matrike razvrstiti v naraščajočem vrstnem redu, njeni elementi pa so v padajočem vrstnem redu. Najslabša časovna zapletenost razvrščanja kopice je O(n log n).

Časovna zapletenost razvrščanja kopice je O (n dnevnik) v vseh treh primerih (najboljšem primeru, povprečnem primeru in najslabšem primeru). Višina celotnega binarnega drevesa z n elementi je miren.

2. Kompleksnost prostora

• Prostorska kompleksnost Heap sortiranja je O(1).

Implementacija Heapsort

Zdaj pa si oglejmo programe Heap sort v različnih programskih jezikih.

Program: Napišite program za izvajanje razvrščanja kopice v jeziku C.

 #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;>