En este artículo, analizaremos el algoritmo Heapsort. La clasificación de montón procesa los elementos creando el montón mínimo o el montón máximo utilizando los elementos de la matriz dada. Min-heap o max-heap representa el orden de la matriz en la que el elemento raíz representa el elemento mínimo o máximo de la matriz.
La ordenacion del monton basicamente realiza de forma recursiva dos operaciones principales:
- Construya un montón H, usando los elementos de la matriz.
- Elimine repetidamente el elemento raíz del montón formado en 1callefase.
Antes de saber más sobre la clasificación del montón, veamos primero una breve descripción de Montón.
¿Qué es un montón?
Un montón es un árbol binario completo, y el árbol binario es un árbol en el que el nodo puede tener como máximo dos hijos. Un árbol binario completo es un árbol binario en el que todos los niveles excepto el último nivel, es decir, el nodo hoja, deben estar completamente llenos y todos los nodos deben estar justificados a la izquierda.
¿Qué es la clasificación del montón?
Heapsort es un algoritmo de clasificación popular y eficiente. El concepto de clasificación del montón es eliminar los elementos uno por uno de la parte del montón de la lista y luego insertarlos en la parte ordenada de la lista.
Heapsort es el algoritmo de clasificación in situ.
entero a cadena en java
Ahora, veamos el algoritmo de clasificación del montón.
Algoritmo
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
ConstruirMaxHeap(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
Funcionamiento del algoritmo de clasificación de montón
Ahora, veamos el funcionamiento del algoritmo Heapsort.
En la clasificación en montón, básicamente, hay dos fases involucradas en la clasificación de elementos. Al utilizar el algoritmo de ordenación del montón, son los siguientes:
- El primer paso incluye la creación de un montón ajustando los elementos de la matriz.
- Después de crear el montón, ahora elimine el elemento raíz del montón repetidamente moviéndolo al final de la matriz y luego almacene la estructura del montón con los elementos restantes.
Ahora veamos en detalle el funcionamiento de la clasificación del montón usando un ejemplo. Para entenderlo más claramente, tomemos una matriz sin clasificar e intentemos ordenarla usando la clasificación de montón. Hará la explicación más clara y sencilla.
Primero, tenemos que construir un montón a partir de la matriz dada y convertirlo en un montón máximo.
Después de convertir el montón dado en el montón máximo, los elementos de la matriz son:
A continuación, tenemos que eliminar el elemento raíz. (89) del montón máximo. Para eliminar este nodo, tenemos que intercambiarlo con el último nodo, es decir. (11). Después de eliminar el elemento raíz, nuevamente tenemos que apilarlo para convertirlo en el montón máximo.
Después de intercambiar el elemento de la matriz 89 con 11, y al convertir el montón en max-heap, los elementos de la matriz son:
En el siguiente paso, nuevamente, tenemos que eliminar el elemento raíz. (81) del montón máximo. Para eliminar este nodo, tenemos que intercambiarlo con el último nodo, es decir. (54). Después de eliminar el elemento raíz, nuevamente tenemos que apilarlo para convertirlo en el montón máximo.
Después de intercambiar el elemento de la matriz 81 con 54 y al convertir el montón en max-heap, los elementos de la matriz son:
En el siguiente paso, tenemos que eliminar el elemento raíz. (76) desde el montón máximo nuevamente. Para eliminar este nodo, tenemos que intercambiarlo con el último nodo, es decir. (9). Después de eliminar el elemento raíz, nuevamente tenemos que apilarlo para convertirlo en el montón máximo.
Después de intercambiar el elemento de la matriz 76 con 9 y al convertir el montón en max-heap, los elementos de la matriz son:
En el siguiente paso, nuevamente tenemos que eliminar el elemento raíz. (54) del montón máximo. Para eliminar este nodo, tenemos que intercambiarlo con el último nodo, es decir. (14). Después de eliminar el elemento raíz, nuevamente tenemos que apilarlo para convertirlo en el montón máximo.
Después de intercambiar el elemento de la matriz 54 con 14 y al convertir el montón en max-heap, los elementos de la matriz son:
En el siguiente paso, nuevamente tenemos que eliminar el elemento raíz. (22) del montón máximo. Para eliminar este nodo, tenemos que intercambiarlo con el último nodo, es decir. (11). Después de eliminar el elemento raíz, nuevamente tenemos que apilarlo para convertirlo en el montón máximo.
Después de intercambiar el elemento de la matriz 22 con 11 y al convertir el montón en max-heap, los elementos de la matriz son:
En el siguiente paso, nuevamente tenemos que eliminar el elemento raíz. (14) del montón máximo. Para eliminar este nodo, tenemos que intercambiarlo con el último nodo, es decir. (9). Después de eliminar el elemento raíz, nuevamente tenemos que apilarlo para convertirlo en el montón máximo.
carpeta de cambio de nombre de Linux
Después de intercambiar el elemento de la matriz 14 con 9 y al convertir el montón en max-heap, los elementos de la matriz son:
En el siguiente paso, nuevamente tenemos que eliminar el elemento raíz. (11) del montón máximo. Para eliminar este nodo, tenemos que intercambiarlo con el último nodo, es decir. (9). Después de eliminar el elemento raíz, nuevamente tenemos que apilarlo para convertirlo en el montón máximo.
Después de intercambiar el elemento de la matriz 11 con 9, los elementos de la matriz son -
Ahora al montón solo le queda un elemento. Después de eliminarlo, el montón estará vacío.
Una vez completada la clasificacion, los elementos de la matriz son:
Ahora, la matriz está completamente ordenada.
Complejidad de clasificación del montón
Ahora, veamos la complejidad temporal de la clasificación de Heap en el mejor de los casos, el caso promedio y el peor de los casos. También veremos la complejidad espacial de Heapsort.
1. Complejidad del tiempo
| Caso | Complejidad del tiempo |
|---|---|
| Mejor caso | En (n registro) |
| Caso promedio | O(n iniciar sesión n) |
| Peor de los casos | O(n iniciar sesión n) |
La complejidad temporal de la clasificación del montón es En (n registro) en los tres casos (mejor caso, caso promedio y peor caso). La altura de un árbol binario completo que tiene n elementos es calma.
2. Complejidad espacial
| Complejidad espacial | O(1) |
| Estable | N0 |
- La complejidad espacial de la clasificación Heap es O (1).
Implementación de Heapsort
Ahora, veamos los programas de tipo Heap en diferentes lenguajes de programación.
Programa: Escriba un programa para implementar la clasificación en montón en lenguaje C.
#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;>