Descripción general
La clasificación del montón es una clasificación de selección de árboles, que es una mejora efectiva en la clasificación de selección directa.
El montón se define de la siguiente manera: una secuencia de n elementos (k1, k2, ..., kn), si y solo si está satisfecho:
Se llama un montón en ese momento. Como se puede ver en la definición del montón, el elemento superior del montón (es decir, el primer elemento) debe ser el elemento más pequeño (montón superior pequeño) o el elemento más grande (montón superior grande).
Si un montón se almacena en una matriz unidimensional, el montón corresponde a un árbol completamente binario, y los valores de todos los nodos no hojas (nodos con niños) no son mayores que (o no menos que) los valores de sus hijos, y los valores del nodo raíz (elemento superior del Heap) son los más pequeños (o más grandes).
(a) Secuencia de montón superior grande: (96, 83, 27, 38, 11, 09)
(b) Secuencia de montón superior pequeño: (12, 36, 24, 85, 47, 30, 53, 91)
Inicialmente, la secuencia de números de N a ordenar se considera un árbol binario almacenado secuencialmente (árbol binario de almacenamiento de matriz unidimensional), ajuste su orden de almacenamiento para que sea un montón, genere el elemento superior del montón para obtener el elemento más pequeño (o más grande) de los elementos de N. Luego reajuste los elementos N-1 restantes para convertirse en un montón, emitir el elemento superior del montón y obtener el elemento que es el segundo pequeño (o el segundo grande) entre los elementos n. Y así sucesivamente hasta que finalmente obtenga una secuencia ordenada con N nodos. Llame a este proceso de montón de proceso.
Pasos y ejemplos
Hay dos problemas para resolver en la implementación de la clasificación de montón:
(1) Cómo construir n números para clasificarse en pilas;
(2) Después de emitir el elemento superior del montón, cómo ajustar los elementos N-1 restantes para que sea un nuevo montón.
Método de montón de construcción (montón superior pequeño):
El proceso de construcción de un montón para la secuencia inicial es un proceso de detección repetida.
Un árbol binario completo de N nodos N, entonces el último nodo es el subárbol del nodo N/2º.
El filtro comienza con el subárbol con el nodo N/2º como la raíz (N/2 es el último nodo con el subárbol), de modo que el subárbol se convierte en un montón.
Luego, filtre los subárboles con cada nodo como raíz en secuencia hacia adelante para que sea un montón hasta el nodo raíz.
Como se muestra en la figura, la secuencia desordenada del proceso inicial de construir un montón: (49, 38, 65, 97, 76, 13, 27, 49)
(a) Secuencia desordenada, Árbol binario inicial, 97 (8/2 = 4 nodo) es el nodo principal del último nodo (49).
(b) 97> = 49, reemplace la posición y luego filtre el nodo anterior 65 de N/2.
(c) 13 <= 27 y 65> = 13, reemplace las posiciones de 65 y 13, y luego reemplace 38 (ambos mayores que no, no se requiere operación), filtro 49.
(d) 13 <= 38 y 49> = 13, reemplace las posiciones de 49 y 13, 49> = 27, reemplace las posiciones de 49 y 27.
(e) Finalmente obtenga un montón, 13 es el número mínimo que obtenemos.
Métodos para ajustar el montón (montón superior pequeño):
Se proporciona un montón de elementos m. Después de emitir los elementos superiores del montón, se dejan elementos M-1. El elemento inferior del montón se alimenta a la parte superior del montón, y el montón se destruye, porque el nodo raíz no cumple con las propiedades del montón.
Intercambie el nodo de la raíz con elementos más pequeños en los subárboles izquierdo y derecho.
Si se intercambia con el subárbol izquierdo: si el montón de subárbol izquierdo está dañado, repita el método (2).
Si se intercambia con el subárbol correcto, repita el método (2) si se destruye el montón de subárbol correcto.
Continúe realizando la operación de intercambio anterior en subárboles que no cumplen con las propiedades del montón hasta que los nodos de la hoja y el montón se construyan.
Para ajustar el montón, solo necesita considerar los nodos corruptos, y no es necesario ajustar otros nodos.
Implementación del código (Java)
Ejecute el código y compare los comentarios con los pasos de ejemplo anteriores para la comparación.
paquete com.coder4j.main; public class HeepSort { / ** * Ajuste a un montón superior pequeño (el resultado es de gran a pequeño después de clasificar) * * @param la matriz es la matriz de montón que se ajustará * @param s es la posición del elemento de la matriz que se ajustará * @param longitud es la longitud de la matriz * * / pública void estatic justs (int s [inth, int sc. tmp = array [s]; int child = 2 * s + 1; // La posición del sistema de nodo infantil izquierdo.out.println ("El nodo a ajustar es: array [" + s + "] =" + tmp); Mientras que (niño <longitud) {// niño + 1 es el niño correcto que actualmente ajusta el nodo // si hay un niño derecho y es más pequeño que el niño izquierdo, use el niño derecho para comparar con el nodo, de lo contrario usa el niño izquierdo si (niño + 1 <longitud && array [niño]> matriz [niño + 1]) {niño ++; } System.out.println ("estará con la matriz infantil [" + child + "] =" + matriz [niño] + "comparar"); // Si el niño más pequeño es más pequeño que este nodo if (array [s]> array [child]) {System.out.println ("El niño es más pequeño que él, posición de intercambio"); matriz [s] = matriz [niño]; // mover al niño más pequeño hacia arriba y reemplazar el nodo actual a ajustar s = niño; // Mueva el nodo ajustado a la posición original de la matriz del niño menor [niño] = tmp; Child = 2 * S + 1; // Continúe juzgando si el nodo a ajustar debe continuar siendo ajustado si (Child> = Longitud) {System.out.println ("No hay hijos, el ajuste ha terminado"); } else {System.out.println ("Continuar comparando con el nuevo niño"); } // continuar; } else {System.out.println ("Los niños son mayores que ellos, el ajuste ha terminado"); ruptar; // El nodo actual que se ajustará es más pequeño que sus hijos izquierdo y derecho, y no es necesario ajustarlo, salir directamente}}}}/ ** * Ajuste a un montón superior grande (el resultado es de pequeño a grande después de clasificar) * * @param matriz es la matriz de arado que se ajusta * @param s es la posición del elemento matriz que se ajusta * @param la longitud es la longitud de la longitud de la longitud de la longitud de la longitud * @param. Heapadjustb (int [] array, int s, int longitud) {int tmp = array [s]; int child = 2 * s + 1; // La posición del sistema de nodo infantil izquierdo.out.println ("El nodo a ajustar es: array [" + s + "] =" + tmp); Mientras que (niño <longitud) {// niño + 1 es el niño correcto que actualmente ajusta el nodo // si hay un niño derecho y es más grande que el niño izquierdo, use el niño derecho para comparar con el nodo, de lo contrario use el niño izquierdo si (niño + 1 <longitud && matra [niño] <matriz [niño + 1]) {niño ++; } System.out.println ("estará con la matriz infantil [" + child + "] =" + matriz [niño] + "comparar"); // Si el niño mayor es más grande que este nodo if (Array [S] <Array [Child]) {System.out.println ("El niño es más grande que él, posición de intercambio"); Array [s] = matriz [niño]; // mover al niño mayor hacia arriba y reemplazar el nodo actual para ajustarse s = niño; // mover el nodo ajustado a la posición original de la matriz de niños mayores [niño] = tmp; Child = 2 * S + 1; // Continúe juzgando si el nodo a ajustar debe ajustarse si (niño> = longitud) {System.out.println ("No hay hijos, el ajuste ha terminado"); } else {System.out.println ("Continuar comparando con el nuevo niño"); } // continuar; } else {System.out.println ("Los niños son más pequeños que ellos, el ajuste ha terminado"); ruptura; // El nodo actual que se ajustará es más grande que sus hijos izquierdo y derecho, y salga directamente sin ajuste}}}/ ** * Algoritmo de clasificación de montón * * @param matriz * @param Inverse True en orden inverso, falso en orden positivo */ public static void Heepsort (int [], boolean inverso) {// inicial stone // la posición de la posición de la posición de la posición de la posición INTRATA INDE INTIMENTA INTIMENTA IMA INTEN INTER. / 2, para ajustar cada nodo hacia arriba para ajustarse al system.out.println ("inicial inicial"); for (int i = (array.length-1) / 2; i> = 0; i--) {if (inverse) {HeapadJusts (Array, I, Array.length); } else {HeapadJustb (Array, I, Array.Length); }} System.out.println ("End de montón inicial"); for (int i = array.length-1; i> 0; i--) {// intercambia el elemento superior del montón h [0] y el último elemento en el montón int tmp = array [i]; matriz [i] = array [0]; matriz [0] = tmp; // Después de cada intercambio del elemento superior del montón y el último elemento en el montón, el montón debe ajustarse si (inverso) {Heapadjusts (matriz, 0, i); } else {HeapadJustb (Array, 0, i); }}} public static void main (string [] args) {int [] array = {49, 38, 65, 97, 76, 13, 27, 49}; Heapsort (matriz, falso); for (int i: array) {system.out.print (i + ""); }}}Resultados de ejecución:
The node to be adjusted at the beginning of the initial heap is: array[3] = 97 The child will be smaller with the child array[7] = 49 The child is smaller with the child, and the node to be adjusted at the end of the adjustment is: array[2] = 65 The child is smaller with the child array[5] = 13 The child is smaller with the child, and the node to be adjusted at the end of the adjustment is: array[1] = 38 El niño es más grande con la matriz del niño [3] = 49 El niño es más grande con la matriz del niño [0] = 49 El niño es más pequeño con la matriz del niño [2] = 13 El niño es más pequeño con la matriz del niño [6] = 27 El niño es más pequeño que la posición de intercambio, y no hay ningún niño en la posición de intercambio. El nodo a ajustar después del ajuste es: matriz [0] = 97 El niño es más pequeño que el niño. El niño es más pequeño que el niño. La posición de intercambio continúa comparando con el nuevo niño. El niño es una matriz [6] = 49 El niño es más pequeño que la posición de intercambio, y no hay un niño en la posición de intercambio. El nodo a ajustar después del ajuste es: matriz [0] = 97 El niño es más pequeño que el niño. El niño es más pequeño que el niño. El niño es más pequeño que el niño. El niño es una matriz [1] = 38 El niño es más pequeño que el niño. El niño es una matriz [3] = 49 El niño es más pequeño que el niño. El niño es más pequeño que la posición de intercambio. El nodo a ajustar después del ajuste es: matriz [0] = 65 El niño es una matriz [1] = 49 El niño es más pequeño que el niño, y la posición de intercambio continúa comparándose con el nuevo niño. El niño será más grande que el niño. El nodo a ajustar después del ajuste es: matriz [0] = 76 El niño es más grande que el niño. El nodo a ajustar después del ajuste es: matriz [0] = 76 El niño es más pequeño que el niño. El nodo a ajustar después del ajuste es: matriz [0] = 49 El niño es más pequeño que el niño. El nodo a ajustar después del ajuste es: matriz [0] = 97 El niño es más pequeño que el niño. El nodo a ajustar después del ajuste es: matriz [0] = 97 76 65 49 49 38 27 13 13
PD: La diferencia entre la clasificación de montón y la clasificación de inserción directa
En el orden de selección directa, para seleccionar el registro con la palabra clave más pequeña de R [1..n], se debe realizar la comparación N-1, y luego seleccionar el registro con la palabra clave más pequeña en R [2..N], se deben realizar comparaciones N-2. De hecho, en las siguientes comparaciones N-2, pueden haberse realizado muchas comparaciones en las comparaciones N-1 anteriores, pero debido a que estos resultados de comparación no se conservaron en el orden anterior, estas operaciones de comparación se repitieron durante el siguiente orden.
La clasificación del montón puede ahorrar parte de los resultados de comparación a través de una estructura de árbol, lo que puede reducir el número de comparaciones.