Para aprender la clasificación del montón, primero debe comprender el concepto de montón. Puede ser aproximado como un método de almacenamiento de matriz como un árbol completamente binario. Pero hay otras propiedades con él, que son similares a los árboles de clasificación binaria. Existen diferencias entre el montón más grande y el montón más pequeño. de su nodo hijo. La clasificación del montón generalmente usa el montón más grande, mientras que el montón más pequeño puede construir una cola de prioridad. Hay un método en el montón que se utiliza para mantener las propiedades del montón, que es el método MaxHeap en nuestro código a continuación. matriz, y el segundo parámetro es ajustar el montón. elementos válidos realmente almacenados en el montón. Tal vez la longitud de la matriz es el número de elementos que realmente se almacenan en el montón, pero no necesariamente todos los datos que necesitamos para construir el montón máximo. La introducción al algoritmo dice que el sub-nodo izquierdo es 2XI, pero nuestra matriz cuenta desde 0, por lo que el sub-nodo izquierdo se convierte en 2XI+1. 2 es, los nodos infantiles de estos puntos son todos los nodos de hoja, por lo que construimos un montón máximo al clasificarlo de abajo hacia arriba. Asegúrese de que todos los nodos en nuestro montón cumplan con las propiedades máximas del montón. Finalmente, la clasificación del montón es eliminar el primer nodo, ordenar los nodos restantes nuevamente y luego eliminar el nodo raíz. Esto asegura que cada vez que lo sacamos, es el valor máximo.
La copia del código es la siguiente:
Clase pública Heepsort {
privado int getleft (int i) {
return 2*i+1;
}
privado int getright (int i) {
return 2*i+2;
}
public void maxheap (int [] Heap, int loc, int size) {
int l = getleft (loc);
int r = getright (loc);
int más grande = loc;
if (l <size && heap [l]> Heap [loc]) {
Más grande = l;
}
if (r <size && heap [r]> Heap [más grande]) {
Más grande = r;
}
if (más grande! = loc) {
int cache = Heap [loc];
Heap [loc] = Heap [más grande];
montón [más grande] = caché;
maxheap (montón, grande, tamaño);
}
}
public void buildHeap (int [] Heap) {
para (int i = Heap.Length/2; i> = 0; i-) {
maxHeap (Heap, I, Heap.length);
}
}
public void sort (int [] Heap) {
BuildHeap (montón);
para (int i = Heap.length-1; i> 1; i-) {
int cache = Heap [0];
Heap [0] = Heap [i];
montón [i] = caché;
maxheap (montón, 0, i);
}
int cache = Heap [0];
montón [0] = montón [1];
montón [1] = caché;
}
public static void main (string [] args) {
int [] Heap = new int [] {4,1,5,3,7,12,65,7};
HeApsort hs = new HeapSort ();
hs.sort (montón);
para (int i = 0; i <heap.length; i ++) {
System.out.println (Heap [i]);
}
}
}