El montón es una estructura importante en la estructura de datos. Después de comprender el concepto y la operación del "montón", puede dominar rápidamente la clasificación de montón.
El concepto de montón
Heap es un árbol binario completo especial. Si los valores de todos los nodos de un árbol completamente binario no son más pequeños que sus hijos, se llama un montón de raíz grande (o un montón superior grande); Si los valores de todos los nodos no son más grandes que sus hijos, se llama un montón de raíz pequeño (o un montón superior pequeño).
En una matriz (almacenar el nodo raíz en el número de subíndice 0), es fácil obtener la siguiente ecuación (estas dos ecuaciones son muy importantes):
1. El nodo con subíndice es I, y las coordenadas del nodo principal son (I-1)/2;
2. El nodo con subíndice es I, las coordenadas del nodo infantil izquierdo son 2*i+1, y el nodo infantil derecho es 2*i+2.
Establecimiento y mantenimiento del montón
El montón puede admitir múltiples operaciones, pero ahora solo nos importan dos problemas:
1. Dada una matriz desordenada, ¿cómo construirlo como un montón?
2. Después de eliminar el elemento superior del montón, ¿cómo ajustar la composición a un nuevo montón?
Veamos primero la segunda pregunta. Supongamos que ya tenemos una gran pila de raíces preparada. Ahora eliminamos el elemento raíz, pero no movemos los otros elementos. Piense en lo que sucedió: el elemento raíz está vacío, pero los otros elementos aún mantienen las propiedades del montón. Podemos mover el último elemento (nombre de código A) a la posición del elemento raíz. Si no es un caso especial, las propiedades del montón se destruyen. Pero esto es simplemente porque A es más pequeño que uno de sus elementos infantiles. Entonces, podemos cambiar un elemento infantil a su posición. Si A es mayor que todos los elementos infantiles, el montón se ajusta; De lo contrario, repita el proceso anterior, el elemento A continúa "hundiéndose" en la estructura del árbol hasta que sea apropiado, y la matriz restaura las propiedades del montón. El proceso anterior generalmente se llama "detección", y la dirección obviamente es de arriba a abajo.
Esto es cierto al eliminar un elemento, y también es insertar un nuevo elemento. La diferencia es que colocamos el nuevo elemento al final y luego lo comparamos con su nodo principal, es decir, filtrarlo de abajo hacia arriba.
Entonces, ¿cómo resolver el primer problema?
Muchos de los libros sobre estructuras de datos que he leído se están filtrando desde el primer nodo no hojas hasta que se filtra el elemento raíz. Este método se llama "Método de filtrado", que requiere elementos de filtrado de bucle N/2.
Pero también podemos aprender de la idea de "crear algo de la nada". Podemos considerar el primer elemento como un montón y luego agregarlo constantemente nuevos elementos. Este método se llama "Método de inserción", que requiere inserción de bucle de elementos (N-1).
Dado que el método de filtrado y el método de inserción son diferentes, los montones que crean son generalmente diferentes para los mismos datos.
Después de una comprensión aproximada del montón, la clasificación del montón es algo natural.
Descripción general del algoritmo/Ideas
Necesitamos una secuencia ascendente, ¿qué debemos hacer? Podemos construir un montón mínimo y luego emitir el elemento raíz cada vez. Sin embargo, este método requiere espacio adicional (de lo contrario, causará mucho movimiento de elementos, y su complejidad se elevará a O (n^2)). ¿Qué pasa si necesitamos una clasificación en el lugar (es decir, no se permite la complejidad del espacio o (n))?
Hay una manera. Podemos construir el montón máximo, y luego generamos el valor máximo en la última posición, y el segundo valor máximo en la última posición ... ya que la salida del elemento máximo cada vez liberará el primer espacio, podemos colocar dicho elemento sin necesidad de espacio adicional. Muy hermosa idea, ¿verdad?
clase pública HeepSort {public static void main (string [] args) {int [] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20}; System.out.println ("Antes de clasificar:"); for (int i = 0; i <arr.length; i ++) {system.out.print (arr [i]+""); } // clasificación de montón Heapsort (arr); System.out.println (); System.out.println ("Después de clasificar:"); for (int i = 0; i <arr.length; i ++) {system.out.print (arr [i]+""); }} / *** sort de montón* / private static void Heapsort (int [] arr) {// construye la secuencia que se clasificará en un montón superior grande para (int i = arr.length / 2; i> = 0; i-) {Heapadjust (arr, i, arr.length); } // Cambia gradualmente el nodo raíz de cada valor máximo con el elemento final, y ajuste el árbol binario para que sea un montón superior grande para (int i = arr.length-1; i> 0; i--) {swap (arr, 0, i); // intercambia el registro superior del montón con el último registro de la subsecuencia actualmente sin clasificar Heapadjust (arr, 0, i); // Después del intercambio, es necesario volver a verificar si el montón cumple con el montón superior. Si no se cumple, debe ajustarse}} / *** Proceso de construcción de la matriz Heap* @param Arr que debe ordenarse* @param I el número del nodo raíz del montón que debe construirse* @param n la longitud de la matriz* / privado estático void void (int [] arr, int i, int n) {int Child; int padre; para (padre = arr [i]; Leftchild (i) <n; i = niño) {child = Leftchild (i); // Si el subárbol izquierdo es más pequeño que el subárbol derecho, debe comparar el subárbol derecho con el nodo principal if (Child! = N - 1 && arr [child] <arr [child+1]) {child ++; // Aumente el número de serie en 1, apuntando al subárbol correcto} // Si el nodo principal es más pequeño que el nodo secundario, debe intercambiar if (padre <arr [child]) {arr [i] = arr [child]; } else {break; // La estructura de montón superior grande no se destruye, no se requiere ajuste}} arr [i] = padre; } // Obtenga el nodo infantil izquierdo privado intent Leftchild (int i) {return 2 * i + 1; } // Posición de elemento de intercambio Private static void swap (int [] arr, int index1, int index2) {int tmp = arr [index1]; arr [index1] = arr [index2]; arr [index2] = tmp; }}