java - codigo - Una comprensión intuitiva de heapsort?
heapsort explicacion (7)
En la escuela, actualmente estamos aprendiendo algoritmos de ordenación en Java y obtuve para mi tarea Heap Sort. Hice mi lectura, traté de averiguar todo lo que pude, pero parece que no puedo captar el concepto.
No te estoy pidiendo que me escribas un programa Java, si pudieras explicarme tan simple como puedes cómo funciona Heap Sort.
Correcto, básicamente haces un montón y sacas el primer nodo en el montón, ya que el primer nodo está garantizado para ser el más grande / más pequeño dependiendo de la dirección de ordenación. Lo complicado es volver a equilibrar / crear el montón en primer lugar.
Se requirieron dos pasos para que yo entendiera el proceso del montón, antes que nada pensar en esto como un árbol, entenderlo, y luego convertir ese árbol en una matriz para que pudiera ser útil.
La segunda parte de esto es esencialmente atravesar la amplitud del árbol primero, de izquierda a derecha, agregando cada elemento al conjunto. Entonces el siguiente árbol:
73
7 12
2 4 9 10
1
Sería {73,7,12,2,4,9,10,1}
La primera parte requiere dos pasos:
- Asegúrese de que cada nodo tenga dos hijos (a menos que no tenga suficientes nodos para hacerlo como en el árbol de arriba).
- Asegúrese de que cada nodo sea más grande (o más pequeño si ordena primero min) que sus elementos secundarios.
Entonces, para heapificar una lista de números, agregue cada uno al montón y luego siga esos dos pasos en orden.
Para crear mi heap arriba, agregaré 10 primero, es el único nodo, así que no hay nada que hacer. Agregue 12 como si fuera un niño a la izquierda:
10
12
Esto satisface 1, pero no 2, así que los cambiaré:
12
10
Agregar 7 - nada que hacer
12
10 7
Agregar 73
12
10 7
73
10 <73, así que es necesario intercambiar esos:
12
73 7
10
12 <73 así que es necesario cambiarlos:
73
12 7
10
Agregar 2 - nada que hacer
73
12 7
10 2
Agregar 4 - nada que hacer
73
12 7
10 2 4
Agregar 9
73
12 7
10 2 4 9
7 <9 - intercambio
73
12 9
10 2 4 7
Agregar 1 - nada que hacer
73
12 9
10 2 4 7
1
Tenemos nuestro montón: D
Ahora simplemente eliminas cada elemento de la parte superior, intercambiando el último elemento con la parte superior del árbol cada vez, y luego reequilibrando el árbol:
Quita 73 - colocando 1 en su lugar
1
12 9
10 2 4 7
1 <12 - así que cambiarlos
12
1 9
10 2 4 7
1 <10 - así que cambiarlos
12
10 9
1 2 4 7
Tome 12 de descuento - reemplace con 7
7
10 9
1 2 4
7 <10 - cambiarlos
10
7 9
1 2 4
Tome 10 de descuento - reemplace con 4
4
7 9
1 2
4 <7 - intercambio
7
4 9
1 2
7 <9 - intercambio
9
4 7
1 2
Tome 9 de descuento - reemplace con 2
2
4 7
1
2 <4 - cambiarlos
4
2 7
1
4 <7 - cambiarlos
7
2 4
1
Tome 7 de descuento - reemplace con 1
1
2 4
1 <4 - cambiarlos
4
2 1
Tome 4 - reemplace con 1
1
2
1 <2 - cambiarlos
2
1
Tome 2 - reemplace con 1
1
Toma 1
Lista ordenada voila.
La clase de ordenamiento incluye la lógica más simple con la complejidad de tiempo O (nlogn) y la complejidad de espacio O (1)
public class HeapSort {
public static void main(String[] args) {
Integer [] a={12,32,33,8,54,34,35,26,43,88,45};
HeapS(a,a.length-1);
System.out.println(Arrays.asList(a));
}
private static void HeapS(Integer[] a, int l) {
if(l<=0)
return;
for (int i = l/2-1; i >=0 ; i--) {
int index=a[2*i+1]>a[2*i+2]?2*i+1:2*i+2;
if(a[index]>a[i]){
int temp=a[index];
a[index]=a[i];
a[i]=temp;
}
}
int temp=a[l];
a[l]=a[0];
a[0]=temp;
HeapS(a,l-1);
}
}
Recuerdo a mi profesor de análisis de Algoritmos para decirnos que el algoritmo de ordenación de montón funciona como un montón de grava:
Imagine que tiene un saco lleno de grava y lo vacía en el piso: las piedras más grandes probablemente rueden hacia el fondo y las piedras más pequeñas (o arena) permanecerán en la parte superior.
Ahora toma la parte superior del montón y guárdalo en el valor más pequeño de tu montón. Vuelva a colocar el resto de su montón en su bolsa y repita. (O puede obtener el enfoque opuesto y agarrar la piedra más grande que vio rodando en el suelo, el ejemplo sigue siendo válido)
Eso es más o menos la manera simple en que sé explicar cómo funciona el montón.
Supongamos que tiene una estructura de datos especial (llamada montón) que le permite almacenar una lista de números y le permite recuperar y eliminar la más pequeña en el tiempo O(lg n) .
¿Ves cómo esto lleva a un algoritmo de clasificación muy simple?
La parte difícil (en realidad no es tan difícil) es implementar el montón.
Tal vez el rastreo interactivo lo ayudará a comprender mejor el algoritmo. Aquí hay una demo .
Una forma de pensar en el tipo de montón es como una versión inteligentemente optimizada del tipo de selección. En la ordenación por selección, el orden funciona al encontrar repetidamente el elemento más grande que aún no se ha colocado correctamente, y luego colocarlo en el siguiente punto correcto de la matriz. Sin embargo, la ordenación por selección se ejecuta en el tiempo O (n 2 ) porque tiene que hacer n rondas para encontrar el elemento más grande de un grupo (y puede haber hasta n elementos diferentes para observar) y colocarlo en su lugar.
Intuitivamente, la ordenación de montones funciona al construir una estructura de datos especial llamada pila binaria que acelera la búsqueda del elemento más grande fuera de los elementos de matriz no colocados. Los montones binarios admiten las siguientes operaciones:
- Insertar , que inserta un elemento en el montón, y
- Delete-Max , que elimina y devuelve el elemento más grande del montón.
En un nivel muy alto, el algoritmo funciona de la siguiente manera:
- Inserte cada elemento de la matriz en un nuevo montón binario.
- Para i = n hasta 1:
- Llame a Delete-Max en el montón para recuperar el elemento más grande del montón.
- Escribe este elemento en la posición i.
Esto ordena la matriz porque los elementos devueltos por Delete-Max están en orden descendente. Una vez que se han eliminado todos los elementos, la matriz se ordena.
La ordenación en montón es eficiente porque las operaciones Insertar y Eliminar máx. En un montón se ejecutan en tiempo O (log n), lo que significa que n inserciones y eliminaciones se pueden realizar en el montón en el tiempo O (n log n). Se puede usar un análisis más preciso para mostrar que, de hecho, toma Θ (n log n) el tiempo independientemente de la matriz de entrada.
Típicamente, el tipo de montón emplea dos optimizaciones principales. En primer lugar, el montón generalmente se crea en el lugar dentro de la matriz al tratar la matriz en sí misma como una representación comprimida del montón. Si observa una implementación heatsort, generalmente verá usos inusuales de índices de matriz basados en multiplicar y dividir por dos; estos accesos funcionan porque tratan la matriz como una estructura de datos condensada. Como resultado, el algoritmo requiere solo O (1) espacio de almacenamiento auxiliar.
En segundo lugar, en lugar de crear el elemento Heap One a la vez, el Heap generalmente se crea utilizando un algoritmo especializado que se ejecuta en el tiempo Θ (n) para construir el Heap in-place. Curiosamente, en algunos casos esto hace que el código sea más fácil de leer porque el código se puede reutilizar, pero el algoritmo en sí mismo se vuelve un poco más complicado de comprender y analizar.
A veces verá Heapsort hecho con un montón ternario . Esto tiene la ventaja de ser un poco más rápido en promedio, pero si encuentras una implementación heapsort usando esto sin saber lo que estás viendo, puede ser bastante difícil de leer. Otros algoritmos también usan la misma estructura general pero una estructura de montón más compleja. Smoothsort usa un montón mucho más complicado para obtener el comportamiento de O (n) en el mejor de los casos al tiempo que mantiene el uso de O (1) espacio y el comportamiento de peor caso O (n log n). La clasificación de álamo es similar a smoothsort, pero con uso de espacio O (log n) y un rendimiento ligeramente mejor. Incluso se pueden pensar en algoritmos de clasificación clásicos, como ordenar por inserción y ordenar por selección como variantes de clasificación de montón .
Una vez que tenga una mejor comprensión de heapsort, es posible que desee examinar el algoritmo introsort , que combina quicksort, heapsort e insert sort para producir un algoritmo de clasificación extremadamente rápido que combina la fuerza del quicksort (clasificación rápida en promedio), heapsort ( excelente comportamiento en el peor de los casos), y tipo de inserción (clasificación rápida para matrices pequeñas). Introsort es lo que se usa en muchas implementaciones de la función std::sort de C ++, y no es muy difícil implementarlo una vez que tiene un heapsort activo.
¡Espero que esto ayude!
Veré cómo respondo esto, porque mi explicación para el tipo de montón y lo que es un montón será un poco ...
... eh, terrible .
De todos modos, en primer lugar, será mejor que verifiquemos qué es un Heap:
Como tomado de Wikipedia , un montón es:
En informática, un montón es una estructura de datos basada en árbol especializada que satisface la propiedad de montón: si B es un nodo secundario de A, entonces la clave (A) ≥ clave (B). Esto implica que un elemento con la mayor clave está siempre en el nodo raíz, por lo que a dicho montón se le llama a veces max-heap. (Alternativamente, si la comparación se invierte, el elemento más pequeño siempre está en el nodo raíz, lo que resulta en un montón mínimo).
Más o menos, un montón es un árbol binario tal que todos los hijos de cualquier nodo son más pequeños que ese nodo.
Ahora, el ordenamiento de montón es un algoritmo de clasificación O ( n lg (n) ). Puedes leer un poco sobre esto here y here . Funciona básicamente al poner todos los elementos de lo que está tratando de clasificar en un montón, y luego construir la matriz ordenada desde el elemento más grande al más pequeño. Continuará reestructurando el montón, y dado que el elemento más grande está en la parte superior (raíz) del montón en todo momento, puede seguir tomando ese elemento y colocarlo en la parte posterior del conjunto ordenado. (Es decir, construirás la matriz ordenada en reversa)
¿Por qué este algoritmo O ( n lg (n) )? Debido a que todas las operaciones en un montón son O ( lg (n) ) y como resultado, realizará n operaciones, lo que resulta en un tiempo de ejecución total de O ( n lg (n) ).
¡Espero que mi terrible diatriba te haya ayudado! Es un poco prolijo Lo siento por eso...