La clasificación del montón se refiere a un algoritmo de clasificación diseñado utilizando la estructura de datos del montón. El apilamiento es una estructura que es aproximadamente completamente binaria y satisface las propiedades del apilamiento: es decir, el valor clave o el índice de un nodo secundario siempre es más pequeño que (o mayor que) su nodo principal.
La complejidad promedio de tiempo de la clasificación de Heap es ο (NLOGN).
Pasos de algoritmo:
1. Crea un montón H [0..N-1]
2. Cambie la cabeza del montón (máximo) y la cola del montón
3. Reduzca el tamaño del montón en 1 y llame a shift_down (0). El propósito es ajustar los datos superiores de la nueva matriz a la posición correspondiente.
4. Repita el paso 2 hasta que el tamaño del montón sea 1
montón:
El montón es en realidad un árbol completamente binario, y cualquier nodo no hojado de su nodo no hojado satisface sus propiedades: clave [i] <= key [2i+1] && key [i] <= key [2i+2] o clave [i]> = key [2i+1] && key> = key [2i+2] Es decir, la palabra clave de cualquier nodo no-loda no es mayor que o menos que la clave de la clave de la tecla. El montón se divide en un montón superior grande y un montón superior pequeño. Una tecla satisfactoria [i]> = clave [2i+1] && Key> = Key [2i+2] se llama un montón superior grande. Una clave satisfactoria [i] <= clave [2i+1] && Key [i] <= Key [2i+2] se llama un montón superior pequeño. De las propiedades anteriores, podemos ver que las palabras clave en la parte superior del montón superior grande son definitivamente las más grandes de todas las palabras clave, y las palabras clave en la parte superior del montón superior pequeño son las más pequeñas de todas las palabras clave.
Idea de clasificación de montón:
La característica de la palabra clave más grande (palabra clave mínima) que se registra en la parte superior del montón superior grande (montón superior pequeño) hace que sea fácil seleccionar el registro más grande (registro mínimo) del desorden cada vez. La idea básica es (el montón superior grande): 1) Construya la secuencia inicial de palabras clave que se clasificará (R1, R2 ... .rn) en un montón superior grande, que es el área desordenada inicial; 2) Intercambie el elemento superior del montón R [1] con el último elemento R [n], y luego obtenga un nuevo área desordenada (R1, R2, ... RN-1) y una nueva región ordenada (RN) y satisfaga R [1,2 ... N-1] <= R [N]; 3) Dado que el nuevo montón superior R [1] después del intercambio puede violar las propiedades del montón, es necesario ajustar el área desordenada actual (R1, R2, ... RN-1) a un nuevo montón, y luego intercambiar R [1] con el último elemento del área desordenada nuevamente para obtener un nuevo área desordenada (R1, R2 ... .rn-2) y una nueva región ordenada (RN-1, RN). Repita este proceso hasta que el número de elementos en el área ordenada sea N-1, y se completa todo el proceso de clasificación. El proceso de operación es el siguiente: 1) Inicializar el montón: construir r [1..n] como un montón; 2) Intercambie el elemento superior del montón R [1] del área no ordenada actual con el último registro en el intervalo, y luego ajuste el nuevo área desordenada a un nuevo montón. Por lo tanto, para la clasificación del montón, las dos operaciones más importantes son construir el montón inicial y ajustar el montón. De hecho, construir el montón inicial es en realidad un proceso de ajuste del montón, pero construir el montón inicial es ajustar todos los nodos no hojas.
Un ejemplo de ilustración
Dada una matriz de configuración a [] = {16,7,3,20,17,8}, el montón lo ordene. Primero, construya un árbol binario completo basado en el elemento de matriz y obtenga
Luego debe construir el montón inicial y luego iniciar el ajuste desde el último nodo no hojado. El proceso de ajuste es el siguiente:
Después del intercambio de 20 y 16, 16 hace que 16 no cumplan con las propiedades del montón, por lo que debe reajustarse.
Esto da el montón inicial.
Cuando se ajusta primero, se convierte en una gran pila superior.
Es decir, cada ajuste es seleccionar el más grande del nodo principal, el nodo infantil izquierdo y el nodo infantil correcto para intercambiar con el nodo principal (después del intercambio, el nodo infantil que se está intercambiando puede hacer que el nodo secundario se intercambie) para no cumplir con la naturaleza del montón, por lo que el nodo infantil que se está intercambiando debe ajustarse nuevamente después de cada intercambio). Con el montón inicial, puede ordenarlo.
En este momento, 3 se encuentra en la parte superior de la pila y las propiedades no están llenas de la pila. Debe ajustar y continuar ajustándose.
De esta manera, todo el intervalo ya es ordenado. En el proceso anterior, podemos ver que la clasificación del montón es en realidad un tipo de clasificación de selección, una clasificación de selección de árboles. Pero para seleccionar directamente el pedido, para seleccionar el registro máximo de R [1 ... n], N-1 Times debe compararse, y luego seleccionar el registro máximo de R [1 ... N-2], es necesario comparar N-2 veces. De hecho, muchas de estas comparaciones N-2 se han realizado en las comparaciones N-1 anteriores, y la clasificación de selección de árboles solo usa las características del árbol para guardar algunos de los resultados de comparación anteriores, por lo que se puede reducir el número de comparaciones. Para n secuencias de palabras clave, en el peor de los casos, cada nodo necesita comparar log2 (n) veces, por lo que su peor complejidad de tiempo es nLogn. La clasificación de Heap es inestable y no es adecuado para clasificar con menos registros. Tanto se ha descrito anteriormente. En resumen, la práctica básica de la clasificación del montón es: Primero, use los datos originales para construir un montón grande (pequeño) como el área original desordenada, y luego, cada vez que el elemento superior del montón se saca y se coloca en el área ordenada. Dado que se saca el elemento superior del montón, colocamos el último elemento en el montón en la parte superior del montón, por lo que se destruyen las propiedades del montón. Necesitamos reajustar el montón y continuar N veces, luego los elementos N en el área no ordenada se colocan en el área ordenada y se completa el proceso de clasificación.
(La pila de edificios es de abajo hacia arriba)
Aplicación práctica:
En la práctica, realizamos una clasificación de montón para obtener el valor máximo o mínimo en ciertas condiciones. Por ejemplo: se deben encontrar 10 valores máximos entre 100 números. Por lo tanto, definimos un montón de tamaño 10, construimos los primeros diez datos en 100 en un montón superior pequeño (la parte superior del montón), y luego lo comparamos con la parte superior del montón de los 11º datos en 100 datos. Si la parte superior del montón es más pequeña que los datos actuales, la parte superior del montón aparece, presione los datos actuales en la parte superior del montón y luego mueva los datos desde la parte superior del montón a una determinada posición.
Código:
public class test0 {static int [] arr; // array, matriz válida public test0 (int m) {arr = new int [m];} static int m = 0; static int size = 0; // Se usa para marcar datos válidos en el hemovinado public void addTosmall (int v) {// int [] a = = {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8,111,222,333,555,66,67,54}; // El tamaño del montón es 10 // ARR = nuevo int [10]; if (size <arr.length) {arr [size] = v; add_sort (size); // add_sort1 (size); size ++;} else {arr [0] = v; add_sort1 (0);}} public void printsmall () {para (int i = 0; i <size; i ++) {system.out.println (arrtsmall) void del () {size-; arr [0] = arr [9]; add_sort1 (0);} public void Small (int index) {if (m <arr.length) {add_sort (index); m ++;} más Coordenadas: Índice *Nódigo infantil izquierdo: índice *2 *Nodo infantil derecho: índice *2+1 *Si el último en la matriz es impar, es el niño izquierdo *Si el último en la matriz es par, es el niño derecho si el nodo secundario es más grande que el nodo principal, el intercambio de valor se realiza. Si el niño derecho es más grande que el niño izquierdo, el intercambio de valor se realiza**/int par; if (index! = 0) {if (índice%2 == 0) {par = (index-1)/2; if (arr [arr [arr]) {swap (arr, index, par); add_sort (par);} if (arr [arr]> arr [par*2]) dex] <arr [par]) {swap (arr, index, par);} add_sort (par);}} else {par = index/2; if (arr [index] <arr [par]) {swap (arr, index, par); add_sort (par);} if (arr [arr [arr [arr [2+1]]) {swap (arr, Índice, index, index, par*2+1); if (arr [index] <arr [par]) {swap (arr, index, par);} add_sort (par);}}}} public void void add_sort1 (int index) {// ajuste pequeño top/*ajuste hacia abajo*siempre que el nodo infantil sea mayor que el valor del nodo principal, el intercambio de valor se realiza,*/into izquierda = INDEX*2; INT*2; INT*2; INT*2; INT = INT*2; INT = INT = INT*2; INT = INT = INT*2; INT = INT*2; INT = INT*2; INT = INT = INT*2; INT = INT*2; INT = INT*2; INT = INT*2+INT = IT INT. max = 0; if (izquierda <10 && arr [izquierda] <arr [index]) {max = izquierda;} else {max = index;} if (derecha <10 && arr [right] <mAx]) {max = right;} if (max! = index) {swap (arr, Índice, index); add_sort1 (max);}}}} tinte; import java.util.scanner; public class main_test0 {public static void main (string args []) {scanner scan = new scanner (system.in); system.out.println ("(pequeño pisos top) por favor ingrese el tamaño de la pata:"); int m = scan.nextint (); test0 test = new test0 (m); int [] a = a = = = = a = a = a = = = = = A = = A = = A = A = A = {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8};for(int i=0;i<a.length;i++){test.addToSmall(a[i]);}test.printSmall();test.del();test.printSmall();scan.close();}}El ejemplo de clasificación de montón de Java anterior (montón superior grande, un montón superior pequeño) es todo el contenido que comparto con usted. Espero que pueda darle una referencia y espero que pueda apoyar más a Wulin.com.