Tässä artikkelissa käsittelemme Heapsort-algoritmia. Keon lajittelu käsittelee elementit luomalla min-keon tai max-keon käyttämällä annetun taulukon elementtejä. Min-heap tai max-heap edustaa taulukon järjestystä, jossa juurielementti edustaa taulukon minimi- tai maksimielementtiä.
Keon lajittelu suorittaa periaatteessa rekursiivisesti kaksi päätoimintoa -
- Rakenna kasa H käyttämällä taulukon elementtejä.
- Poista toistuvasti kohdassa 1 muodostetun kasan juurielementtistvaihe.
Ennen kuin tiedät enemmän keon lajittelusta, katsotaanpa ensin lyhyt kuvaus Pino.
Mikä on kasa?
Kasa on täydellinen binääripuu, ja binääripuu on puu, jossa solmulla voi olla korkeintaan kaksi lasta. Täydellinen binääripuu on binääripuu, jossa kaikki tasot paitsi viimeinen taso, eli lehtisolmu, tulee olla täysin täytettyinä ja kaikkien solmujen tulee olla vasemmalle tasattuina.
Mikä on kasalajittelu?
Heapsort on suosittu ja tehokas lajittelualgoritmi. Keon lajittelun ideana on poistaa elementit yksitellen listan kasaosasta ja lisätä ne sitten luettelon lajiteltuun osaan.
Heapsort on paikan päällä tapahtuva lajittelualgoritmi.
Madhuri sanoi, tule
Katsotaanpa nyt kason lajittelun algoritmia.
Algoritmi
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
Keon lajittelualgoritmin toiminta
Katsotaanpa nyt Heapsort-algoritmin toimintaa.
Kasalajittelussa elementtien lajittelussa on periaatteessa kaksi vaihetta. Keon lajittelualgoritmia käyttämällä ne ovat seuraavat -
- Ensimmäinen vaihe sisältää kasan luomisen säätämällä taulukon elementtejä.
- Keon luomisen jälkeen poista nyt keon juurielementti toistuvasti siirtämällä se taulukon loppuun ja tallenna sitten keon rakenne jäljellä olevien elementtien kanssa.
Katsotaanpa nyt kasalajittelun toimintaa yksityiskohtaisesti esimerkin avulla. Ymmärtääksesi sen selkeämmin, otetaan lajittelematon taulukko ja yritetään lajitella se keon lajittelulla. Se tekee selityksestä selkeämmän ja helpomman.
Ensin meidän on rakennettava kasa annetusta taulukosta ja muutettava se maksimikekoksi.
Kun annettu kasa on muutettu maksimikekoksi, taulukon elementit ovat -
Seuraavaksi meidän on poistettava juurielementti (89) maksimikasasta. Tämän solmun poistamiseksi meidän on vaihdettava se viimeisen solmun kanssa, ts. (yksitoista). Kun juurielementti on poistettu, meidän on jälleen kasoitettava se, jotta se muunnetaan maksimikekoksi.
Matriisielementin vaihdon jälkeen 89 kanssa yksitoista, ja muuntamalla kasan max-kekoksi taulukon elementit ovat -
Seuraavassa vaiheessa meidän on jälleen poistettava juurielementti (81) maksimikasasta. Tämän solmun poistamiseksi meidän on vaihdettava se viimeisen solmun kanssa, ts. (54). Kun juurielementti on poistettu, meidän on taas kasoitettava se, jotta se muunnetaan maksimikekoksi.
Matriisielementin vaihdon jälkeen 81 kanssa 54 ja muuntamalla kasan max-kekoksi taulukon elementit ovat -
Seuraavassa vaiheessa meidän on poistettava juurielementti (76) taas max-kasasta. Tämän solmun poistamiseksi meidän on vaihdettava se viimeisen solmun kanssa, ts. (9). Kun juurielementti on poistettu, meidän on taas kasoitettava se, jotta se muunnetaan maksimikekoksi.
java trimmausmerkkijono
Matriisielementin vaihdon jälkeen 76 kanssa 9 ja muuntamalla kasan max-kekoksi taulukon elementit ovat -
Seuraavassa vaiheessa meidän on jälleen poistettava juurielementti (54) maksimikasasta. Tämän solmun poistamiseksi meidän on vaihdettava se viimeisen solmun kanssa, ts. (14). Kun juurielementti on poistettu, meidän on taas kasoitettava se, jotta se muunnetaan maksimikekoksi.
Matriisielementin vaihdon jälkeen 54 kanssa 14 ja muuntamalla kasan max-kekoksi taulukon elementit ovat -
Seuraavassa vaiheessa meidän on jälleen poistettava juurielementti (22) maksimikasasta. Tämän solmun poistamiseksi meidän on vaihdettava se viimeisen solmun kanssa, ts. (yksitoista). Kun juurielementti on poistettu, meidän on taas kasoitettava se, jotta se muunnetaan maksimikekoksi.
Matriisielementin vaihdon jälkeen 22 kanssa yksitoista ja muuntamalla kasan max-kekoksi taulukon elementit ovat -
Seuraavassa vaiheessa meidän on jälleen poistettava juurielementti (14) maksimikasasta. Tämän solmun poistamiseksi meidän on vaihdettava se viimeisen solmun kanssa, ts. (9). Kun juurielementti on poistettu, meidän on taas kasoitettava se, jotta se muunnetaan maksimikekoksi.
Matriisielementin vaihdon jälkeen 14 kanssa 9 ja muuntamalla kasan max-kekoksi taulukon elementit ovat -
Seuraavassa vaiheessa meidän on jälleen poistettava juurielementti (yksitoista) maksimikasasta. Tämän solmun poistamiseksi meidän on vaihdettava se viimeisen solmun kanssa, ts. (9). Kun juurielementti on poistettu, meidän on taas kasoitettava se, jotta se muunnetaan maksimikekoksi.
Matriisielementin vaihdon jälkeen yksitoista kanssa 9, taulukon elementit ovat -
Nyt kasassa on vain yksi elementti jäljellä. Sen poistamisen jälkeen kasa on tyhjä.
Lajittelun jälkeen taulukon elementit ovat -
Nyt matriisi on täysin lajiteltu.
Keon lajittelun monimutkaisuus
Katsotaan nyt keon lajittelun aikamonimutkaisuus parhaassa tapauksessa, keskimääräisessä tapauksessa ja pahimmassa tapauksessa. Näemme myös Heapsortin avaruuden monimutkaisuuden.
1. Aika monimutkaisuus
| Asia | Aika monimutkaisuus |
|---|---|
| Paras tapaus | O(n log) |
| Keskimääräinen tapaus | O(n log n) |
| Pahimmassa tapauksessa | O(n log n) |
Keon lajittelun aika monimutkaisuus on O(n log) kaikissa kolmessa tapauksessa (paras tapaus, keskimääräinen tapaus ja huonoin tapaus). Täydellisen binääripuun, jossa on n elementtiä, korkeus on rauhoittaa.
2. Tilan monimutkaisuus
| Avaruuden monimutkaisuus | O(1) |
| Vakaa | N0 |
- Keon lajittelun avaruuden monimutkaisuus on O(1).
Heapsortin käyttöönotto
Katsotaanpa nyt Keon ohjelmia lajiteltuina eri ohjelmointikielillä.
Ohjelmoida: Kirjoita ohjelma keon lajittelun toteuttamiseksi C-kielellä.
#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;>