Ebben a cikkben a Heapsort algoritmusról fogunk beszélni. A kupac rendezés úgy dolgozza fel az elemeket, hogy az adott tömb elemei felhasználásával létrehozza a min-heap vagy max-heap elemet. Min-heap vagy max-heap a tömb sorrendjét jelenti, amelyben a gyökérelem a tömb minimális vagy maximális elemét jelenti.

A halomrendezés alapvetően rekurzív módon két fő műveletet hajt végre -

• Építsünk egy H kupacot a tömb elemeinek felhasználásával.
• Az 1-ben képzett kupac gyökérelemét ismételten törölje^utcafázis.

Mielőtt többet tudna meg a kupac rendezéséről, lássuk először annak rövid leírását Halom.

Mi az a kupac?

A kupac egy teljes bináris fa, a bináris fa pedig olyan fa, amelyben a csomópontnak a legnagyobb két gyermeke lehet. A teljes bináris fa olyan bináris fa, amelyben az utolsó szint, azaz a levélcsomópont kivételével az összes szintet teljesen ki kell tölteni, és az összes csomópontot balra kell igazítani.

Mi az a kupac rendezés?

A Heapssort egy népszerű és hatékony rendezési algoritmus. A kupac rendezés fogalma az, hogy az elemeket egyenként eltávolítjuk a lista kupac részéből, majd beillesztjük a lista rendezett részébe.

A Heapssort a helyben történő rendezési algoritmus.

távolítsa el az excel első karakterét

Most pedig lássuk a kupacrendezés algoritmusát.

Algoritmus

 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 

A kupacrendezési algoritmus működése

Most pedig lássuk a Heapsort algoritmus működését.

A kupacrendezésben alapvetően két fázis vesz részt az elemek rendezésében. A kupacrendezési algoritmus használatával ezek a következők:

• Az első lépés egy kupac létrehozása a tömb elemeinek beállításával.
• A kupac létrehozása után most ismételten távolítsa el a kupac gyökérelemét a tömb végére tolva, majd tárolja a kupacszerkezetet a többi elemmel együtt.

Most egy példa segítségével nézzük meg részletesen a kupacrendezés működését. Hogy érthetőbb legyen, vegyünk egy rendezetlen tömböt, és próbáljuk meg rendezni a kupacrendezés segítségével. Világosabbá és könnyebbé teszi a magyarázatot.

Először az adott tömbből egy kupacot kell alkotnunk, és max kupacsá kell alakítanunk.

Az adott kupac max kupacsá alakítása után a tömb elemei:

Ezután törölnünk kell a gyökérelemet (89) a max kupacból. Ennek a csomópontnak a törléséhez fel kell cserélnünk az utolsó csomóponttal, pl. (tizenegy). A gyökérelem törlése után ismét fel kell halmozni, hogy max kupacsá alakítsuk.

A tömbelem cseréje után 89 val vel tizenegy, és a kupacot max-halommá alakítva a tömb elemei:

A következő lépésben ismét törölnünk kell a gyökérelemet (81) a max kupacból. Ennek a csomópontnak a törléséhez fel kell cserélnünk az utolsó csomóponttal, pl. (54). A gyökérelem törlése után ismét fel kell halmozni, hogy max kupacsá alakítsuk.

A tömbelem cseréje után 81 val vel 54 és a kupacot max-halommá alakítva a tömb elemei:

A következő lépésben törölnünk kell a gyökérelemet (76) ismét a max kupacból. Ennek a csomópontnak a törléséhez fel kell cserélnünk az utolsó csomóponttal, pl. (9). A gyökérelem törlése után ismét fel kell halmozni, hogy max kupacsá alakítsuk.

A tömbelem cseréje után 76 val vel 9 és a kupacot max-halommá alakítva a tömb elemei:

A következő lépésben ismét törölnünk kell a gyökérelemet (54) a max kupacból. Ennek a csomópontnak a törléséhez fel kell cserélnünk az utolsó csomóponttal, pl. (14). A gyökérelem törlése után ismét fel kell halmozni, hogy max kupacsá alakítsuk.

A tömbelem cseréje után 54 val vel 14 és a kupacot max-halommá alakítva a tömb elemei:

A következő lépésben ismét törölnünk kell a gyökérelemet (22) a max kupacból. Ennek a csomópontnak a törléséhez fel kell cserélnünk az utolsó csomóponttal, pl. (tizenegy). A gyökérelem törlése után ismét fel kell halmozni, hogy max kupacsá alakítsuk.

A tömbelem cseréje után 22 val vel tizenegy és a kupacot max-halommá alakítva a tömb elemei:

A következő lépésben ismét törölnünk kell a gyökérelemet (14) a max kupacból. Ennek a csomópontnak a törléséhez fel kell cserélnünk az utolsó csomóponttal, pl. (9). A gyökérelem törlése után ismét fel kell halmozni, hogy max kupacsá alakítsuk.

A tömbelem cseréje után 14 val vel 9 és a kupacot max-halommá alakítva a tömb elemei:

A következő lépésben ismét törölnünk kell a gyökérelemet (tizenegy) a max kupacból. Ennek a csomópontnak a törléséhez fel kell cserélnünk az utolsó csomóponttal, pl. (9). A gyökérelem törlése után ismét fel kell halmozni, hogy max kupacsá alakítsuk.

A tömbelem cseréje után tizenegy val vel 9, a tömb elemei:

Most a kupacnak csak egy eleme maradt. A törlés után a kupac üres lesz.

A rendezés befejezése után a tömb elemei:

Most a tömb teljesen rendezve van.

bájtok a python karakterlánchoz

Halomrendezés bonyolultsága

Most lássuk a kupac rendezés időbeli összetettségét a legjobb, az átlagos és a legrosszabb esetben. Látni fogjuk a Heapsort térbonyolultságát is.

1. Időbonyolultság

Legjobb eset összetettsége –Akkor fordul elő, ha nincs szükség rendezésre, azaz a tömb már rendezve van. A halomrendezés legjobb eseti időbonyolultsága az O(n log). Átlagos ügykomplexitás -Ez akkor fordul elő, ha a tömb elemei összekeveredett sorrendben vannak, ami nem megfelelően növekvő és nem megfelelően csökkenő sorrendben van. A kupacrendezés átlagos eset-idő-bonyolultsága a O(n log n). A legrosszabb eset összetettsége -Ez akkor fordul elő, ha a tömbelemeket fordított sorrendben kell rendezni. Ez azt jelenti, hogy tegyük fel, hogy a tömb elemeit növekvő sorrendbe kell rendeznie, de az elemei csökkenő sorrendben vannak. A halomrendezés legrosszabb időbeli összetettsége az O(n log n).

A kupacrendezés időbonyolultsága az O(n log) mindhárom esetben (legjobb, átlagos és legrosszabb esetben). Egy n elemű teljes bináris fa magassága a nyugodt.

2. A tér összetettsége

• A Heap rendezés térkomplexitása O(1).

Heapsort megvalósítása

Most pedig lássuk a Heap programjait különböző programozási nyelveken.

Program: Írjon programot a kupacrendezés megvalósítására C nyelven.

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