clasificación de montón es una técnica de clasificación basada en comparación basada en montón binario estructura de datos. Es similar al clasificación de selección donde primero encontramos el elemento mínimo y colocamos el elemento mínimo al principio. Repita el mismo proceso para los elementos restantes.
Algoritmo de clasificación de montón
Para resolver el problema siga la siguiente idea:
Problema recomendado Por favor, resuélvalo en la PRÁCTICA primero, antes de pasar a la solución Resolver el problemaPrimero convierta la matriz en una estructura de datos del montón usando heapify, luego, uno por uno, elimine el nodo raíz del Max-heap y reemplácelo con el último nodo del montón y luego apile la raíz del montón. Repita este proceso hasta que el tamaño del montón sea mayor que 1.
- Construya un montón a partir de la matriz de entrada dada.
- Repita los siguientes pasos hasta que el montón contenga solo un elemento:
- Intercambie el elemento raíz del montón (que es el elemento más grande) con el último elemento del montón.
- Elimina el último elemento del montón (que ahora está en la posición correcta).
- Apila los elementos restantes del montón.
- La matriz ordenada se obtiene invirtiendo el orden de los elementos en la matriz de entrada.
Trabajo detallado de clasificación de montón
Para comprender la ordenación en montón con mayor claridad, tomemos una matriz sin clasificar e intentemos ordenarla usando la ordenación en montón.
Considere la matriz: arr[] = {4, 10, 3, 5, 1}.Construya un árbol binario completo: Construya un árbol binario completo a partir de la matriz.
Algoritmo de clasificación de montón | Construya un árbol binario completo
Transformar en montón máximo: Después de eso, la tarea es construir un árbol a partir de esa matriz desordenada e intentar convertirlo en montón máximo.
- Para transformar un montón en un montón máximo, el nodo principal siempre debe ser mayor o igual que los nodos secundarios.
- Aquí, en este ejemplo, como nodo padre 4 es más pequeño que el nodo hijo 10, por lo tanto, cámbielos para construir un montón máximo.
- Ahora, 4 como padre es más pequeño que el niño 5 , por lo tanto, intercambie ambos nuevamente y el montón y la matriz resultantes deberían ser así:
Algoritmo de clasificación de montón | Árbol binario construido por Max Heapify
Realizar clasificación de montón: Elimine el elemento máximo en cada paso (es decir, muévalo a la posición final y elimínelo) y luego considere los elementos restantes y transfórmelos en un montón máximo.
- Eliminar el elemento raíz (10) del montón máximo. Para eliminar este nodo, intente intercambiarlo con el último nodo, es decir. (1). Después de eliminar el elemento raíz, vuelva a apilarlo para convertirlo en el montón máximo.
- El montón y la matriz resultantes deberían verse así:
Algoritmo de clasificación de montón | Eliminar el máximo de la raíz y el máximo de apilamiento
- Repita los pasos anteriores y se verá como lo siguiente:
Algoritmo de clasificación de montón | Eliminar el siguiente máximo de root nad max heapify
s en pitón
- Ahora elimine la raíz (es decir, 3) nuevamente y realice heapify.
Algoritmo de clasificación de montón | Repita el paso anterior
- Ahora, cuando se elimina la raíz una vez más, se ordena. y la matriz ordenada será como arreglo[] = {1, 3, 4, 5, 10} .
Algoritmo de clasificación de montón | Matriz ordenada final
Implementación de clasificación de montón
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[mayor]) mayor = l; // Si el hijo derecho es mayor que el mayor // hasta ahora if (r< N && arr[r]>arr[mayor]) mayor = r; // Si el más grande no es raíz if (¡el más grande! = i) { swap(arr[i], arr[el más grande]); // acumular recursivamente el // subárbol afectado heapify(arr, N, más grande); } } // Función principal para ordenar el montón void heapSort(int arr[], int N) { // Construir el montón (reorganizar la matriz) para (int i = N / 2 - 1; i>= 0; i--) montón (arr, N, i); // Uno por uno extrae un elemento // del montón for (int i = N - 1; i> 0; i--) { // Mueve la raíz actual para finalizar swap(arr[0], arr[i]); // llama a max heapify en el montón reducido heapify(arr, i, 0); } } // Una función de utilidad para imprimir una matriz de tamaño n 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[más grande]) más grande = izquierda; // Si el hijo derecho es mayor que el mayor // hasta ahora if (right< N && arr[right]>arr[más grande]) más grande = derecha; // Intercambiar y continuar acumulando // si la raíz no es la más grande // Si la más grande no es la raíz if (¡más grande!= i) { swap(&arr[i], &arr[más grande]); // acumular recursivamente el // subárbol afectado heapify(arr, N, más grande); } } // Función principal para ordenar el montón void heapSort(int arr[], int N) { // Construir el montón máximo para (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // Ordenación del montón para (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Heapify elemento raíz // para obtener el elemento más alto en // raíz nuevamente heapify(arr, i, 0); } } // Una función de utilidad para imprimir una matriz de tamaño n 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--) heapify(arr, N, i); // Uno por uno extrae un elemento del montón for (int i = N - 1; i> 0; i--) { // Mover la raíz actual al final int temp = arr[0]; arreglo[0] = arreglo[i]; llegada[i] = temperatura; // llama a max heapify en el montón reducido heapify(arr, i, 0); } } // Para amontonar un subárbol enraizado con el nodo i que es // un índice en arr[]. n es el tamaño del montón void heapify(int arr[], int N, int i) { int más grande = i; // Inicializa el mayor como raíz int l = 2 * i + 1; // izquierda = 2*i + 1 int r = 2 * i + 2; // derecha = 2*i + 2 // Si el hijo izquierdo es mayor que la raíz if (l< N && arr[l]>arr[mayor]) mayor = l; // Si el hijo derecho es mayor que el mayor hasta el momento if (r< N && arr[r]>arr[mayor]) mayor = r; // Si el más grande no es raíz if (¡más grande! = i) { int swap = arr[i]; arr[i] = arr[más grande]; arr[más grande] = intercambiar; // amontonar recursivamente el subárbol afectado heapify(arr, N, más grande); } } /* Una función de utilidad para imprimir una matriz de tamaño n */ static void printArray(int arr[]) { int N = arr.length; para (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--) heapify(arr, N, i); // Uno por uno extrae un elemento del montón for (int i = N - 1; i> 0; i--) { // Mover la raíz actual al final int temp = arr[0]; arreglo[0] = arreglo[i]; llegada[i] = temperatura; // llama a max heapify en el montón reducido heapify(arr, i, 0); } } // Para amontonar un subárbol enraizado con el nodo i que es // un índice en arr[]. n es el tamaño del montón void heapify(int[] arr, int N, int i) { int más grande = i; // Inicializa el mayor como raíz int l = 2 * i + 1; // izquierda = 2*i + 1 int r = 2 * i + 2; // derecha = 2*i + 2 // Si el hijo izquierdo es mayor que la raíz if (l< N && arr[l]>arr[mayor]) mayor = l; // Si el hijo derecho es mayor que el mayor hasta el momento if (r< N && arr[r]>arr[mayor]) mayor = r; // Si el más grande no es raíz if (¡más grande! = i) { int swap = arr[i]; arr[i] = arr[más grande]; arr[más grande] = intercambiar; // apila recursivamente el subárbol afectado heapify(arr, N, más grande); } } /* Una función de utilidad para imprimir una matriz de tamaño n */ static void printArray(int[] arr) { int N = arr.Length; para (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--) heapify(arr, N, i); // Uno por uno extrae un elemento del montón for (var i = N - 1; i> 0; i--) { // Mover la raíz actual al final var temp = arr[0]; arreglo[0] = arreglo[i]; llegada[i] = temperatura; // llama a max heapify en el montón reducido heapify(arr, i, 0); } } // Para amontonar un subárbol enraizado con el nodo i que es // un índice en arr[]. n es el tamaño de la función del montón heapify(arr, N, i) { var más grande = i; // Inicializa el mayor como raíz var l = 2 * i + 1; // izquierda = 2*i + 1 var r = 2 * i + 2; // derecha = 2*i + 2 // Si el hijo izquierdo es mayor que la raíz if (l< N && arr[l]>arr[mayor]) mayor = l; // Si el hijo derecho es mayor que el mayor hasta el momento if (r< N && arr[r]>arr[mayor]) mayor = r; // Si el más grande no es raíz if (¡más grande! = i) { var swap = arr[i]; arr[i] = arr[más grande]; arr[más grande] = intercambiar; // apila recursivamente el subárbol afectado heapify(arr, N, más grande); } } /* Una función de utilidad para imprimir una matriz de tamaño n */ function printArray(arr) { var N = arr.length; para (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[$mayor]) $mayor = $l; // Si el hijo derecho es mayor que el mayor hasta el momento if ($r< $N && $arr[$r]>$arr[$más grande]) $más grande = $r; // Si el mayor no es root if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$mayor]; $arr[$más grande] = $intercambio; // acumular recursivamente el subárbol afectado heapify($arr, $N, $largest); } } // función principal para ordenar el montón function heapSort(&$arr, $N) { // Construir el montón (reorganizar la matriz) para ($i = $N / 2 - 1; $i>= 0; $i- -) montón($arr, $N, $i); // Uno por uno extrae un elemento del montón for ($i = $N-1; $i> 0; $i--) { // Mover la raíz actual al final $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // llama a max heapify en el montón reducido heapify($arr, $i, 0); } } /* Una función de utilidad para imprimir una matriz de tamaño n */ 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 ?>> Python3 # Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def 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 # See if left child of root exists and is # greater than root if l < N and arr[largest] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < N and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, N, largest) # The main function to sort an array of given size def heapSort(arr): N = len(arr) # Build a maxheap. for i in range(N//2 - 1, -1, -1): heapify(arr, N, i) # One by one extract elements for i in range(N-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0) # Driver's code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] # Function call heapSort(arr) N = len(arr) print('Sorted array is') for i in range(N): print('%d' % arr[i], end=' ') # This code is contributed by Mohit Kumra> Producción
Sorted array is 5 6 7 11 12 13>
Análisis de complejidad de Ordenar montón
Complejidad del tiempo: O(N iniciar sesión N)
Espacio Auxiliar: O (log n), debido a la pila de llamadas recursiva. Sin embargo, el espacio auxiliar puede ser O(1) para una implementación iterativa.
Puntos importantes sobre Heap Sort:
- La clasificación de montón es un algoritmo local.
- Su implementación típica no es estable pero se puede hacer estable (Ver este )
- Normalmente entre 2 y 3 veces más lento que el que se implementa bien Ordenación rápida . La razón de la lentitud es la falta de localidad de referencia.
Ventajas de la clasificación en montón:
- Complejidad del tiempo eficiente: Heap Sort tiene una complejidad temporal de O (n log n) en todos los casos. Esto lo hace eficiente para ordenar grandes conjuntos de datos. El iniciar sesión sustantivo, masculino— El factor proviene de la altura del montón binario y garantiza que el algoritmo mantenga un buen rendimiento incluso con una gran cantidad de elementos.
- Uso de memoria - El uso de memoria puede ser mínimo (escribiendo un heapify() iterativo en lugar de uno recursivo). Entonces, aparte de lo necesario para contener la lista inicial de elementos a ordenar, no necesita espacio de memoria adicional para funcionar.
- Simplicidad – Es más sencillo de entender que otros algoritmos de clasificación igualmente eficientes porque no utiliza conceptos informáticos avanzados como la recursividad.
Desventajas de la clasificación en montón:
- Costoso : La clasificación en montón es costosa ya que las constantes son más altas en comparación con la clasificación por fusión, incluso si la complejidad del tiempo es O (n Log n) para ambos.
- Inestable : La clasificación del montón es inestable. Podría reorganizar el orden relativo.
- Eficiente: Heap Sort no es muy eficiente cuando se trabaja con datos muy complejos.
Preguntas frecuentes relacionadas con la clasificación del montón
P1. ¿Cuáles son las dos fases de Heap Sort?
java agregar a una matriz
El algoritmo de clasificación del montón consta de dos fases. En la primera fase, la matriz se convierte en un montón máximo. Y en la segunda fase, se elimina el elemento más alto (es decir, el que está en la raíz del árbol) y los elementos restantes se usan para crear un nuevo montón máximo.
P2. ¿Por qué Heap Sort no es estable?
El algoritmo de ordenación del montón no es un algoritmo estable porque intercambiamos arr[i] con arr[0] en heapSort() lo que podría cambiar el orden relativo de las claves equivalentes.
P3. ¿Es Heap Sort un ejemplo del algoritmo Divide and Conquer?
La clasificación del montón es NO en absoluto un algoritmo divide y vencerás. Utiliza una estructura de datos de montón para ordenar eficientemente sus elementos y no un enfoque de dividir y conquistar para ordenar los elementos.
P4. ¿Qué algoritmo de clasificación es mejor: clasificación en montón o clasificación por combinación?
La respuesta está en la comparación de su complejidad temporal y sus necesidades espaciales. La clasificación por combinación es ligeramente más rápida que la clasificación por montón. Pero, por otro lado, la clasificación por combinación requiere memoria adicional. Dependiendo del requisito, se debe elegir cuál utilizar.
P5. ¿Por qué la clasificación por montón es mejor que la clasificación por selección?
La clasificación por montón es similar a la clasificación por selección, pero con una mejor manera de obtener el máximo de elementos. Aprovecha la estructura de datos del montón para obtener el máximo elemento en tiempo constante.