logo

TechCodeview

Keon lajittelu – Tietorakenteiden ja algoritmien opetusohjelmat

Kasan lajittelu on vertailuun perustuva lajittelutekniikka, joka perustuu Binäärikeko tietorakenne. Se on samanlainen kuin valinta lajittelu jossa etsitään ensin minimielementti ja sijoitetaan minimielementti alkuun. Toista sama prosessi muille elementeille.

Keon lajittelualgoritmi

Ratkaise ongelma noudattamalla alla olevaa ideaa:



Muunna ensin taulukko keon tietorakenteeksi käyttämällä kasaa, poista sitten yksitellen Max-keon juurisolmu ja korvaa se keon viimeisellä solmulla ja kasaa sitten kasan juuri. Toista tämä prosessi, kunnes kasan koko on suurempi kuin 1.

  • Rakenna kasa annetusta syöttötaulukosta.
  • Toista seuraavat vaiheet, kunnes kasa sisältää vain yhden elementin:
    • Vaihda keon juurielementti (joka on suurin elementti) keon viimeisellä elementillä.
    • Poista kasan viimeinen elementti (joka on nyt oikeassa asennossa).
    • Kasaa loput kasan elementit.
  • Lajiteltu taulukko saadaan vaihtamalla syöttötaulukon elementtien järjestys.
Suositeltu ongelma Ratkaise se ensin kohdassa PRACTICE, ennen kuin siirryt ratkaisuun Ratkaise ongelma

Kekon lajittelun yksityiskohtainen työskentely

Ymmärtääksesi keon lajittelun selkeämmin, otetaan lajittelematon taulukko ja yritetään lajitella se keon lajittelulla.
Tarkastellaan taulukkoa: arr[] = {4, 10, 3, 5, 1}.

Rakenna täydellinen binaaripuu: Rakenna taulukosta täydellinen binääripuu.



Keon lajittelualgoritmi | Rakenna täydellinen binaaripuu

Muunna maksimikekoksi: Sen jälkeen tehtävänä on rakentaa puu tästä lajittelemattomasta taulukosta ja yrittää muuntaa se muotoon max kasa.

  • Jos haluat muuntaa keon enimmäiskekoksi, pääsolmun tulee aina olla suurempi tai yhtä suuri kuin alisolmut
    • Tässä, tässä esimerkissä, pääsolmuna 4 on pienempi kuin lapsisolmu 10, siten, vaihda ne rakentaaksesi maksimikasan.
  • Nyt, 4 koska vanhempi on pienempi kuin lapsi 5 , joten vaihda nämä molemmat uudelleen ja tuloksena olevan kasan ja taulukon pitäisi olla tällainen:

Keon lajittelualgoritmi | Max Heapifyn rakentama binääripuu



merkkijono java

Suorita kasalajittelu: Poista maksimielementti kussakin vaiheessa (eli siirrä se ääriasentoon ja poista se) ja harkitse sitten loput elementit ja muunna se maksimikasoksi.

  • Poista juurielementti (10) maksimikasasta. Jos haluat poistaa tämän solmun, yritä vaihtaa se viimeisen solmun kanssa, ts. (1). Kun olet poistanut juurielementin, kasa se uudelleen, jotta se muuntaa maksimikeon.
    • Tuloksena olevan kasan ja taulukon pitäisi näyttää tältä:

Keon lajittelualgoritmi | Poista maksimi juuresta ja max heapify

  • Toista yllä olevat vaiheet ja se näyttää tältä:

Keon lajittelualgoritmi | Poista seuraava maksimi juuresta nad max heapify

  • Poista nyt juuri (eli 3) uudelleen ja suorita kasapainotus.

Keon lajittelualgoritmi | Toista edellinen vaihe

  • Nyt kun juuri poistetaan, se on lajiteltu. ja lajiteltu matriisi on sellainen arr[] = {1, 3, 4, 5, 10} .

Keon lajittelualgoritmi | Lopullinen lajiteltu matriisi

Kekon lajittelun käyttöönotto

C++ 
// C++ program for implementation of Heap Sort #include  using namespace std; // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) {  // Initialize largest as root  int largest = i;  // left = 2*i + 1  int l = 2 * i + 1;  // right = 2*i + 2  int r = 2 * i + 2;  // If left child is larger than root  if (l < N && arr[l]>arr[suurin]) suurin = l;  // Jos oikea lapsi on suurempi kuin suurin // tähän mennessä if (r< N && arr[r]>arr[suurin]) suurin = r;  // Jos suurin ei ole juuri if (suurin != i) { swap(arr[i], arr[suurin]);  // Rekursiivisesti kasaa vaikuttanut // alipuu heapify(arr, N, suurin);  } } // Pääfunktio keon lajitteluun void heapSort(int arr[], int N) { // Rakenna pino (järjestä array) kohteelle (int i = N / 2 - 1; i>= 0; i--) kasaa(arr, N, i);  // Poimi yksitellen elementin // kasosta for (int i = N - 1; i> 0; i--) { // Siirrä nykyinen juuri swap(arr[0], arr[i]);  // kutsu max heapifyta vähennetyssä kasassa heapify(arr, i, 0);  } } // Aputoiminto n-koon taulukon tulostamiseen void printArray(int arr[], int N) { for (int i = 0; i< N; ++i)  cout << arr[i] << ' ';  cout << '
'; } // Driver's code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int N = sizeof(arr) / sizeof(arr[0]);  // Function call  heapSort(arr, N);  cout << 'Sorted array is 
';  printArray(arr, N); }>
C 
// Heap Sort in C #include  // Function to swap the position of two elements void swap(int* a, int* b) {  int temp = *a;  *a = *b;  *b = temp; } // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) {  // Find largest among root,  // left child and right child  // Initialize largest as root  int largest = i;  // left = 2*i + 1  int left = 2 * i + 1;  // right = 2*i + 2  int right = 2 * i + 2;  // If left child is larger than root  if (left < N && arr[left]>arr[suurin]) suurin = vasen;  // Jos oikea lapsi on suurempi kuin suurin // tähän mennessä if (oikea< N && arr[right]>arr[suurin]) suurin = oikea;  // Vaihda ja jatka pinotusta // jos juuri ei ole suurin // Jos suurin ei ole juuri if (suurin != i) { swap(&arr[i], &arr[suurin]);  // Rekursiivisesti kasaa vaikuttanut // alipuu heapify(arr, N, suurin);  } } // Pääfunktio keon lajitteluun void heapSort(int arr[], int N) { // Rakenna maksimikeko kohteelle (int i = N / 2 - 1; i>= 0; i--) pino(arr , N, i);  // Keon lajittelu for (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]);  // Kasaa juurielementti // saadaksesi korkeimman elementin // root taas heapify(arr, i, 0);  } } // Aputoiminto n-koon taulukon tulostamiseen void printArray(int arr[], int N) { for (int i = 0; i< N; i++)  printf('%d ', arr[i]);  printf('
'); } // Driver's code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int N = sizeof(arr) / sizeof(arr[0]);  // Function call  heapSort(arr, N);  printf('Sorted array is
');  printArray(arr, N); } // This code is contributed by _i_plus_plus_.>
Java 
// Java program for implementation of Heap Sort public class HeapSort {  public void sort(int arr[])  {  int N = arr.length;  // Build heap (rearrange array)  for (int i = N / 2 - 1; i>= 0; i--) kasaa(arr, N, i);  // Poimi yksitellen elementin kasasta for (int i = N - 1; i> 0; i--) { // Siirrä nykyinen juuri loppuun int temp = arr[0];  arr[0] = arr[i];  arr[i] = lämpötila;  // kutsu max heapifyta vähennetyssä kasassa heapify(arr, i, 0);  } } // Kasoittaa alipuu, jonka juuret ovat solmulla i, joka on // indeksi arr[]:ssa. n on kasan koko void kasaa(int arr[], int N, int i) { int suurin = i; // Alusta suurin juurena int l = 2 * i + 1; // vasen = 2*i + 1 int r = 2 * i + 2; // oikea = 2*i + 2 // Jos vasen lapsi on suurempi kuin juuri if (l< N && arr[l]>arr[suurin]) suurin = l;  // Jos oikea lapsi on suurempi kuin suurin tähän mennessä if (r< N && arr[r]>arr[suurin]) suurin = r;  // Jos suurin ei ole juuri if (suurin != i) { int swap = arr[i];  arr[i] = arr[suurin];  arr[suurin] = swap;  // Rekursiivisesti kasaa vaikuttanut alipuu heapify(arr, N, suurin);  } } /* Aputoiminto, jolla tulostetaan taulukko, jonka koko on n */ staattinen void printArray(int arr[]) { int N = arr.length;  for (int i = 0; i< N; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver's code  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int N = arr.length;  // Function call  HeapSort ob = new HeapSort();  ob.sort(arr);  System.out.println('Sorted array is');  printArray(arr);  } }>
C# 
// C# program for implementation of Heap Sort using System; public class HeapSort {  public void sort(int[] arr)  {  int N = arr.Length;  // Build heap (rearrange array)  for (int i = N / 2 - 1; i>= 0; i--) kasaa(arr, N, i);  // Poimi yksitellen elementin kasasta for (int i = N - 1; i> 0; i--) { // Siirrä nykyinen juuri loppuun int temp = arr[0];  arr[0] = arr[i];  arr[i] = lämpötila;  // kutsu max heapifyta vähennetyssä kasassa heapify(arr, i, 0);  } } // Kasoittaa alipuu, jonka juuret ovat solmulla i, joka on // indeksi arr[]:ssa. n on kasan koko void heapify(int[] arr, int N, int i) { int suurin = i; // Alusta suurin juurena int l = 2 * i + 1; // vasen = 2*i + 1 int r = 2 * i + 2; // oikea = 2*i + 2 // Jos vasen lapsi on suurempi kuin juuri if (l< N && arr[l]>arr[suurin]) suurin = l;  // Jos oikea lapsi on suurempi kuin suurin tähän mennessä if (r< N && arr[r]>arr[suurin]) suurin = r;  // Jos suurin ei ole juuri if (suurin != i) { int swap = arr[i];  arr[i] = arr[suurin];  arr[suurin] = swap;  // Rekursiivisesti kasaa vaikuttanut alipuu heapify(arr, N, suurin);  } } /* Aputoiminto, jolla tulostetaan taulukko, jonka koko on n */ staattinen void printArray(int[] arr) { int N = arr.Length;  for (int i = 0; i< N; ++i)  Console.Write(arr[i] + ' ');  Console.Read();  }  // Driver's code  public static void Main()  {  int[] arr = { 12, 11, 13, 5, 6, 7 };  int N = arr.Length;  // Function call  HeapSort ob = new HeapSort();  ob.sort(arr);  Console.WriteLine('Sorted array is');  printArray(arr);  } } // This code is contributed // by Akanksha Rai(Abby_akku)>
Javascript 
// JavaScript program for implementation // of Heap Sort  function sort( arr)  {  var N = arr.length;  // Build heap (rearrange array)  for (var i = Math.floor(N / 2) - 1; i>= 0; i--) kasaa(arr, N, i);  // Poimi yksitellen elementin kasasta kohteelle (var i = N - 1; i> 0; i--) { // Siirrä nykyinen juuri loppuun var temp = arr[0];  arr[0] = arr[i];  arr[i] = lämpötila;  // kutsu max heapifyta vähennetyssä kasassa heapify(arr, i, 0);  } } // Kasoittaa alipuu, jonka juuret ovat solmulla i, joka on // indeksi arr[]:ssa. n on kasafunktion koko heapify(arr, N, i) { var suurin = i; // Alustus suurin juurina var l = 2 * i + 1; // vasen = 2*i + 1 var r = 2 * i + 2; // oikea = 2*i + 2 // Jos vasen lapsi on suurempi kuin juuri if (l< N && arr[l]>arr[suurin]) suurin = l;  // Jos oikea lapsi on suurempi kuin suurin tähän mennessä if (r< N && arr[r]>arr[suurin]) suurin = r;  // Jos suurin ei ole juuri if (suurin != i) { var swap = arr[i];  arr[i] = arr[suurin];  arr[suurin] = swap;  // Rekursiivisesti kasaa vaikuttanut alipuu heapify(arr, N, suurin);  } } /* Aputoiminto n-koon taulukon tulostamiseen */ funktio printArray(arr) { var N = arr.length;  for (var i = 0; i< N; ++i)  document.write(arr[i] + ' ');    }  var arr = [12, 11, 13, 5, 6, 7];  var N = arr.length;  sort(arr);  document.write( 'Sorted array is');  printArray(arr, N); // This code is contributed by SoumikMondal>
PHP 
 // Php program for implementation of Heap Sort // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(&$arr, $N, $i) { $largest = $i; // Initialize largest as root $l = 2*$i + 1; // left = 2*i + 1 $r = 2*$i + 2; // right = 2*i + 2 // If left child is larger than root if ($l < $N && $arr[$l]>$arr[$suurin]) $suurin = $l; // Jos oikea lapsi on suurempi kuin suurin tähän mennessä if ($r< $N && $arr[$r]>$arr[$suurin]) $suurin = $r; // Jos suurin ei ole juuri if ($suurin != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$suurin]; $arr[$suurin] = $vaihto; // Kasaa rekursiivisesti vaikuttava alipuu heapify($arr, $N, $suurin); } } // pääfunktio keon lajittelufunktion tekemiseen hepSort(&$arr, $N) { // Rakenna pino (järjestä array) kohteelle ($i = $N / 2 - 1; $i>= 0; $i- -) kasaa($arr, $N, $i); // Poimi yksitellen elementin kasasta kohteelle ($i = $N-1; $i> 0; $i--) { // Siirrä nykyinen juuri loppuun $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $lämpötila; // kutsu max heapifyta vähennetyssä kasassa heapify($arr, $i, 0); } } /* Aputoiminto n-koon taulukon tulostamiseen */ function printArray(&$arr, $N) { for ($i = 0; $i< $N; ++$i) echo ($arr[$i].' ') ; } // Driver's program $arr = array(12, 11, 13, 5, 6, 7); $N = sizeof($arr)/sizeof($arr[0]); // Function call heapSort($arr, $N); echo 'Sorted array is ' . '
'; printArray($arr , $N); // This code is contributed by Shivi_Aggarwal ?>>>Python 3
Lähtö 
Sorted array is 5 6 7 11 12 13>

Monimutkaisuusanalyysi Keon lajittelu

Aika monimutkaisuus: O(N log N)
Aputila: O(log n), johtuen rekursiivisesta kutsupinosta. Iteratiivisen toteutuksen aputila voi kuitenkin olla O(1).

Tärkeitä seikkoja Kekolajittelusta:

  • Keon lajittelu on paikallaan oleva algoritmi.
  • Sen tyypillinen toteutus ei ole vakaa, mutta se voidaan tehdä vakaaksi (katso Tämä )
  • Tyypillisesti 2-3 kertaa hitaampi kuin hyvin toteutettu QuickSort . Hitauden syynä on referenssipaikan puute.

Kasalajittelun edut:

  • Tehokas ajan monimutkaisuus: Keon lajittelun aikamonimutkaisuus on O(n log n) kaikissa tapauksissa. Tämä tekee siitä tehokkaan suurten tietojoukkojen lajittelussa. The loki n tekijä tulee binäärikeon korkeudesta, ja se varmistaa, että algoritmi säilyttää hyvän suorituskyvyn myös suurella määrällä elementtejä.
  • Muistin käyttö - Muistin käyttö voi olla minimaalista (kirjoittamalla iteratiivinen heapify() rekursiivisen sijaan). Joten lukuun ottamatta sitä, mikä on välttämätöntä lajiteltujen kohteiden alkuperäisen luettelon säilyttämiseksi, se ei tarvitse ylimääräistä muistitilaa toimiakseen
  • Yksinkertaisuus - Se on helpompi ymmärtää kuin muut yhtä tehokkaat lajittelualgoritmit, koska se ei käytä edistyneitä tietojenkäsittelytieteen käsitteitä, kuten rekursiota.

Kasalajittelun haitat:

  • Kallista : Keon lajittelu on kallista, koska vakiot ovat korkeammat verrattuna yhdistämislajitteluun, vaikka molempien aikamonimutkaisuus on O(n Log n).
  • Epävakaa : Keon lajittelu on epävakaa. Se saattaa muuttaa suhteellista järjestystä.
  • Tehokas: Keon lajittelu ei ole kovin tehokasta, kun käsitellään erittäin monimutkaisia ​​tietoja.

Keon lajitteluun liittyvät usein kysytyt kysymykset

Q1. Mitkä ovat kasalajittelun kaksi vaihetta?

Keon lajittelualgoritmi koostuu kahdesta vaiheesta. Ensimmäisessä vaiheessa taulukko muunnetaan maksimikasoksi. Ja toisessa vaiheessa korkein elementti poistetaan (eli puun juurella oleva) ja jäljellä olevia elementtejä käytetään uuden maksimikeon luomiseen.

Q2. Miksi Heap Sort ei ole vakaa?

Keon lajittelualgoritmi ei ole vakaa algoritmi, koska vaihdamme arr[i]:n arr[0]:n kanssa hepSort():ssa, mikä saattaa muuttaa vastaavien avainten suhteellista järjestystä.

Q3. Onko Heap Sort esimerkki hajota ja hallitse -algoritmista?

Kasan lajittelu on EI ylipäänsä hajota ja hallitse -algoritmi. Se käyttää elementtien tehokkaaseen lajitteluun kasatietorakennetta eikä elementtien lajittelemiseen hajota ja hallitse -lähestymistapaa.

Q4. Kumpi lajittelualgoritmi on parempi – Kekolajittelu vai Yhdistämislajittelu?

Vastaus löytyy niiden aikamonimutkaisuuden ja tilavaatimusten vertailusta. Yhdistämislajittelu on hieman nopeampi kuin Keko-lajittelu. Mutta toisaalta yhdistäminen vie ylimääräistä muistia. Vaatimuksesta riippuen kannattaa valita kumpaa käyttää.

Q5. Miksi Keon lajittelu on parempi kuin valintalajittelu?

Keon lajittelu on samanlainen kuin valintalajittelu, mutta sillä on parempi tapa saada suurin elementti. Se hyödyntää keon tietorakennetta saadakseen maksimielementin vakioajassa

javan nimeämiskäytäntö