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öljeutcafá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
| Ügy | Idő összetettsége |
|---|---|
| Legjobb eset | O(n log) |
| Átlagos eset | O(n log n) |
| Legrosszabb esetben | 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 tér összetettsége | O(1) |
| Stabil | N0 |
- 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 'i' is the index of root node in array a[], and 'n' 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 >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 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 'i' is the index of root node in array a[], and 'n' 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 >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 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 'i' is the index of root node in array a[], and 'n' 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 >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 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 'i' is the index of root node in array a[], and 'n' 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 >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 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's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>