heap sort c with examples
Introducció a l’ordenació en pila amb exemples.
Heapsort és una de les tècniques de classificació més eficients. Aquesta tècnica crea un munt a partir de la matriu no classificada donada i, a continuació, torna a utilitzar-lo per ordenar la matriu.
Heapsort és una tècnica d’ordenació basada en la comparació i que utilitza un munt binari.
=> Llegiu la sèrie de formació Easy C ++.
arguments de línia d'ordres en exemples de seqüència de comandaments
Què aprendreu:
- Què és un munt binari?
- Algorisme general
- Il·lustració
- Exemple C ++
- Exemple de Java
- Conclusió
- Lectura recomanada
Què és un munt binari?
Un munt binari es representa mitjançant un arbre binari complet. Un arbre binari complet és un arbre binari en què tots els nodes de cada nivell estan completament omplerts, excepte els nodes de fulla i els nodes es queden a l'esquerra.
Un munt binari o simplement un munt és un arbre binari complet on els elements o nodes s’emmagatzemen de manera que el node arrel sigui més gran que els seus dos nodes fills. Això també s'anomena heap màxim.
Els elements del munt binari també es poden emmagatzemar com a min-munt en què el node arrel és més petit que els seus dos nodes fills. Podem representar un munt com un arbre binari o una matriu.
Tot representant un munt com a matriu, suposant que l’índex comença a 0, l’element arrel s’emmagatzema a 0. En general, si un node pare es troba a la posició I, el node fill esquerre es troba a la posició (2 * I + 1) i el node dret és a (2 * I +2).
Algorisme general
A continuació es mostra l'algoritme general per a la tècnica de classificació en pila.
- Creeu un munt màxim a partir de les dades donades de manera que l'arrel sigui l'element més alt del munt.
- Traieu l’arrel, és a dir, l’element més alt del munt i substituïu-lo o canvieu-lo per l’últim element del munt.
- A continuació, ajusteu la pila màxima per no infringir les propietats de la pila màxima (heapify).
- El pas anterior redueix la mida de l'emmagatzematge dinàmic en 1.
- Repetiu els tres passos anteriors fins que la mida de l'emmagatzematge dinàmic es redueixi a 1.
Com es mostra a l'algorisme general per ordenar el conjunt de dades donat per ordre creixent, primer construïm un munt màxim per a les dades donades.
Prenguem un exemple per construir un munt màxim amb el conjunt de dades següent.
6, 10, 2, 4, 1
Podem construir un arbre per a aquest conjunt de dades de la següent manera.
A la representació d'arbre anterior, els números entre claudàtors representen les posicions respectives de la matriu.
Per tal de construir un munt màxim de la representació anterior, hem de complir la condició d’emmagatzematge dinàmic que el node pare ha de ser superior als seus nodes fills. En altres paraules, hem de 'amuntegar' l'arbre per convertir-lo a max-heap.
Després de l'amuntegament de l'arbre anterior, obtindrem el màxim amunt com es mostra a continuació.
Com es mostra més amunt, tenim aquest màxim acumulat generat a partir d’una matriu.
A continuació, presentem una il·lustració d'una mena de tipus. Un cop vista la construcció de max-heap, saltarem els passos detallats per construir un max-heap i mostrarem directament el màxim de cada pas.
Il·lustració
Penseu en la següent matriu d'elements. Hem d’ordenar aquesta matriu mitjançant la tècnica d’ordenació en pila.
Construïm un max-heap com es mostra a continuació per ordenar la matriu.
Un cop construït el munt, el representem en forma de matriu, tal com es mostra a continuació.
Ara comparem l’1cnode (arrel) amb l'últim node i després canvieu-los. Així, tal com es mostra més amunt, canviem 17 i 3 de manera que 17 estigui a la darrera posició i 3 estigui a la primera posició.
Ara traiem el node 17 del munt i el posem a la matriu ordenada tal com es mostra a la part ombrejada de sota.
Ara tornem a construir un munt per als elements de la matriu. Aquesta vegada, la mida de l'emmagatzematge dinàmic es redueix en 1, ja que hem suprimit un element (17) de l'emmagatzematge dinàmic.
A continuació es mostra el munt dels elements restants.
Al següent pas, repetirem els mateixos passos.
Comparem i intercanviem l'element arrel i l'últim element del munt.
Després d'intercanviar, suprimim l'element 12 de l'emmagatzematge dinàmic i el desplaçem a la matriu ordenada.
Preguntes tècniques sobre l'entrevista c ++
Una vegada més, construïm un munt màxim per als elements restants, tal com es mostra a continuació.
Ara intercanviem l’arrel i l’últim element, és a dir, el 9 i el 3. Després d’intercanviar, l’element 9 s’elimina del munt i es posa en una matriu ordenada.
En aquest moment, només tenim tres elements al munt, tal com es mostra a continuació.
Intercanviem 6 i 3 i suprimim l’element 6 del munt i l’afegim a la matriu ordenada.
Ara construïm un munt dels elements restants i, a continuació, intercanviem tots dos.
Després d’intercanviar 4 i 3, suprimim l’element 4 del munt i l’afegim a la matriu ordenada. Ara només ens queda un node al munt, tal com es mostra a continuació .
De manera que ara només queda un node, el suprimim del munt i l’afegim a la matriu ordenada.
Per tant, el que es mostra anteriorment és la matriu ordenada que hem obtingut com a resultat de la classificació en pila.
A la il·lustració anterior, hem ordenat la matriu en ordre ascendent. Si hem d'ordenar la matriu en ordre descendent, hem de seguir els mateixos passos però amb el min-heap.
L’algorisme de Heapsort és idèntic al tipus de selecció en què seleccionem l’element més petit i el situem en una matriu ordenada. Tanmateix, l’ordenació en pila és més ràpida que la de selecció pel que fa al rendiment. Ho podem dir ja que Hacksort és una versió millorada del tipus de selecció.
A continuació, implementarem Heapsort en llenguatge C ++ i Java.
La funció més important en ambdues implementacions és la funció 'heapify'. Aquesta funció és cridada per la rutina principal de gran muntatge per reordenar el subarbre un cop es suprimeix un node o quan es construeix max-heap.
Quan hàgim amuntat l'arbre correctament, només podrem obtenir els elements correctes en les seves posicions adequades i, per tant, la matriu s'ordenarà correctament.
Exemple C ++
A continuació es mostra el codi C ++ per a la implementació de heapsort.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Sortida:
Matriu d’entrada
4 17 3 12 9 6
Matriu ordenada
3 4 6 9 12 17
A continuació, implementarem el heapsort en llenguatge Java
Exemple de Java
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr()) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr(), int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { int swap = arr(root); arr(root) = arr(largest); arr(largest) = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr()) { int n = arr.length; for (int i=0; i Sortida:
Matriu d'entrada:
4 17 3 12 9 6
Matriu ordenada:
com obrir el fitxer json a Windows
3 4 6 9 12 17
Conclusió
Heapsort és una tècnica d’ordenació basada en la comparació que utilitza un muntatge binari.
Es pot anomenar com una millora respecte a la selecció, ja que aquestes dues tècniques de classificació funcionen amb una lògica similar: trobar l’element més gran o més petit de la matriu repetidament i després col·locar-lo a la matriu ordenada.
L’ordenació en pila fa servir max-heap o min-heap per ordenar la matriu. El primer pas en l'ordenació de l'emmagatzematge dinàmic és crear un amunt mínim o màxim a partir de les dades de la matriu i, a continuació, suprimir l'element arrel recursivament i amuntegar-lo fins que només hi hagi un node present a l'emmagatzematge dinàmic.
Heapsort és un algorisme eficient i funciona més ràpidament que el tipus de selecció. Es pot utilitzar per ordenar una matriu gairebé ordenada o trobar k elements més grans o més petits de la matriu.
Amb això, hem completat el nostre tema sobre tècniques d’ordenació en C ++. A partir del proper tutorial, començarem amb les estructures de dades una per una.
=> Cerqueu aquí tota la sèrie de formació C ++.
Lectura recomanada
- MongoDB Sort () Mètode amb exemples
- Ordre d'ordenació Unix amb sintaxi, opcions i exemples
- Combina l’ordenació en C ++ amb exemples
- Ordenació de shell en C ++ amb exemples
- Ordre d'inserció a C ++ amb exemples
- Selecció Ordena en C ++ amb exemples
- Classificació de bombolles en C ++ amb exemples
- Ordena ràpidament en C ++ amb exemples