1. Conocimiento básico
Lo que generalmente llamamos un montón se refiere a un montón binario, que también se llama un árbol binario completo o un árbol binario aproximadamente completo. El montón binario se divide en el montón más grande y el montón más pequeño.
La clasificación del montón se refiere a un algoritmo de clasificación diseñado utilizando la estructura de datos de Heap, que es un tipo de selección de clasificación. Puede localizar rápidamente elementos del índice especificado utilizando las características de la matriz. Las matrices pueden obtener directamente elementos basados en el índice, y la complejidad del tiempo es O (1), es decir, constantes, por lo que son extremadamente eficientes para la adquisición de valor.
Las características del montón máximo son las siguientes:
Las características del montón mínimo son las siguientes:
2. pensamiento de algoritmo
1. La idea del algoritmo del montón más grande es:
Primero, el R [0 ... N-1] inicial está integrado en el montón más grande. En este momento, es un montón desordenado. La parte superior del montón es el elemento más grande y luego se intercambia el último registro R [N-1] del área no ordenada. Esto da como resultado el nuevo área desordenada R [0 ... N-2] y el área ordenada R [N-1], y satisface R [0 ... N-2]. Keyeys ≤ R [N-1] .Key.
Dado que el primer R [0 ... N-2] puede no satisfacer las propiedades del montón máximo después del intercambio, el primer R [0 ... N-2] se ajusta al montón máximo hasta que solo se ajusta el último elemento de R [0].
Después de completar el tipo máximo de montón, es en realidad una secuencia ascendente. Cada vez que se ajusta el montón, se obtiene el elemento más grande y luego se intercambia con el último elemento del montón de corriente. Por lo tanto, la secuencia final obtenida es una secuencia ascendente.
2. La idea del algoritmo del montón más pequeño es:
Primero, el R [0 ... N-1] inicial está integrado en el montón más pequeño. En este momento, es un montón desordenado. El elemento superior del montón es el elemento más pequeño y luego intercambia el top R [0] con la última r [n-1] del área no ordenada, obteniendo así el nuevo montón no ordenado R [0 ... n-2] y el montón ordenado R [n-1], y satisfaciendo R [0 ... n-2] .Keys> = r [n-1] .key.
Dado que el primer R [0 ... N-2] puede no cumplir con las propiedades del montón mínimo después del intercambio, el primer R [0 ... N-2] se ajusta al montón mínimo hasta que solo se ajusta el último elemento de R [0] y se clasifica el montón mínimo. Después de completar el pedido del montón mínimo, en realidad es una secuencia descendente. Cada vez que se ajusta el montón, se obtiene el elemento más pequeño y luego se intercambia con el último elemento del montón no ordenado actual, por lo que la secuencia obtenida está en orden descendente.
Consejo: El proceso de clasificación del montón es en realidad el proceso de expandir continuamente el área ordenada, y luego reducir continuamente el área desordenada hasta que solo haya áreas ordenadas.
3. Análisis de procesos de clasificación
Debido a que el algoritmo es relativamente abstracto, aquí ilustramos directamente el proceso de clasificación de montón dando un pequeño ejemplo. A continuación, usamos esta secuencia desordenada para usar el montón más grande para la clasificación de montón, y la secuencia resultante es la secuencia ascendente (ASC).
Secuencia desordenada: 89, -7,999, -89,7,0, -888,7, -7
Paso 1: Inicialice el montón máximo para construir:
Paso 2: intercambie el elemento máximo 999 en la parte superior del montón con el último elemento del área no ordenada, de modo que 999 se convierte en un área ordenada. Después del intercambio, -7 se convierte en la parte superior del montón. Dado que -7 no es el elemento más grande en el área no ordenada, es necesario ajustar el área no ordenada para que el valor máximo 89 en el área no ordenada se convierta en la parte superior del montón, por lo que -7 y 89 se intercambian. Después del intercambio, el subárbol correcto de 89 no cumple con las propiedades del montón más grande, por lo que el subárbol correcto debe ajustarse al montón más grande, por lo que -7 debe intercambiarse con 0, como se muestra en la figura a continuación:
De la cifra, cuando -7% 89% de intercambio, la parte superior de la pila es el elemento más grande, pero el hijo izquierdo de -7 es 0 y el niño derecho es -888. Desde -7 <0, el nodo -7 no cumple con las propiedades del montón, por lo que debe ajustarse. Entonces, 0 se intercambia con -7.
Luego repita el segundo paso hasta que se convierta en un área ordenada.
Finalmente: lo que se obtiene es una secuencia ascendente
4. Complejidad del tiempo
El tiempo de clasificación del montón se compone principalmente de la sobrecarga de tiempo de establecer el montón inicial y ajustar repetidamente el montón. Dado que la clasificación del montón es inestable, la complejidad del tiempo que obtiene será mayor según la situación real, por lo que solo puede tomar la complejidad promedio de tiempo.
La complejidad del tiempo promedio es: O (N * log2 (n))
Las operaciones que requieren mucho tiempo de la clasificación del montón incluyen: montón inicial + ajuste repetido del montón, y la complejidad del tiempo es la siguiente:
1. Edificio del montón inicial: cada nodo principal se comparará e intercambiará con los nodos infantiles izquierdo y derecho por hasta 2 veces, por lo que la complejidad está relacionada con el número de nodos principales. Basado en 2x <= n (x es el número de veces que los elementos se pueden plegar por la mitad, es decir, el número de nodos principales), se obtiene x = log2n. Es decir, o (log2n)
2. Ajuste repetido del montón: dado que los resultados de la comparación de la matriz se registran durante la inicialización del montón, el tipo de montón no es sensible al orden de la matriz de la secuencia original, y la mejor situación es similar al peor de los casos. El elemento superior del montón debe extraerse N-1 veces. Cada vez que se toma el elemento superior del montón, el montón debe reconstruirse (o (reconstruir montón) <o (montón inicial)). Así que menos que o (n-1) * o (log2n)
Uso recomendado:
Dado que la cantidad de veces se debe comparar la inicialización del montón, la clasificación del montón es más adecuada para situaciones en las que la cantidad de datos es muy grande (millones de datos o más). Dado que la clasificación rápida eficiente se basa en la implementación recursiva, se produce un error de desbordamiento de pila cuando el volumen de datos es muy grande.
5. Código de muestra de Java
clase pública HeepSort {private static int [] sort = new int [] {1,0,10,20,3,5,6,4,9,8,12, 17,34,11}; public static void main (string [] args) {buildmaxHeapifify (sort); Heapsort (sort); imprimir (ordenar); } private static void buildMaxHeapify (int [] data) {// Solo aquellos sin niños necesitan crear el montón máximo, comenzar desde el último nodo principal int intartindex = getParentIndex (data.length-1); // Cree el máximo de la intemperie desde el final, y es el montón correcto para (int i = startIndex; i> = 0; i) {maxheapify (data data. }}/***Crear el montón máximo**@paramdata*@paramheapsize requiere el tamaño del montón máximo, que generalmente se usa en la clasificación, porque el valor máximo se coloca al final, el final ya no se clasifica como el máximo de losmádicos*@paramindex. punto con los nodos infantiles izquierdo y derecho int int right = getChildRightIndex (índice); int más grande = índice; if (left <thedepsize && data [index] <data [izquierda]) {lefty = izquierda; } if (right <thedepsize && data [más grande] <data [right]) {más grande = right; } // Después de obtener el valor máximo, es posible que deba intercambiar. Si se intercambia, sus hijos pueden no ser el montón más grande. Debe reajustarse si (más grande! = Index) {int temp = data [index]; datos [índice] = datos [más grande]; datos [más grande] = temp; maxHeapify (datos, calentamiento, más grande); }} /***Clasificación, el valor máximo se coloca al final. Aunque los datos son el montón más grande, se vuelve incremental después de clasificar * *@paramdata */private static void Heapsort (int [] data) {// intercambia con el encabezado al final, ajuste el montón máximo después del intercambio para (int i = data.length-1; i> 0; i-) {int temp = data [0]; datos [0] = datos [i]; datos [i] = temp; maxHeapify (datos, i, 0); }} / ** *paramCurrent *@return * / private static int getParentIndex (int current) {return (current-1) >> 1; } / ** *Posición actual del nodo infantil preste atención a los paréntesis, y la prioridad de adición es mayor * *@paramcurrent *@return * / private static int getChildleftIndex (int cursion) {return (actual << 1) +1; } / ** *Posición del nodo infantil correcto * *@paramcurrent *@return * / private static int getChildRightIndex (int curtent) {return (actual << 1) +2; } Private static void print (int [] data) {int pre = -2; for (int i = 0; i <data.length; i ++) {if (pre <(int) getLog (i+1)) {pre = (int) getLog (i+1); System.out.println (); } System.out.print (datos [i]+"|"); }}/** *logotipo con base 2 * *@paraparam *@return */private static double getLog (doble param) {return math.log (param) /math.log (2); }}