Estructuras de datos y algoritmos: montón y clasificación de montón

Heap sort es un algoritmo de clasificación in situ con una complejidad temporal de O(nlogn).

Un montón es un tipo especial de árbol.

Siempre que se cumplan los dos puntos siguientes, es un montón:

Para un montón en el que el valor de cada nodo es mayor o igual al valor de cada nodo en el subárbol, lo llamamos "Pila grande". Un montón en el que el valor de cada nodo es menor o igual que el valor de cada nodo en el subárbol se denomina "montón mini-max".

Los árboles binarios completos son más adecuados para el almacenamiento en matrices. El uso de una matriz para almacenar un árbol binario completo ahorra espacio de almacenamiento. Los subíndices pueden contar directamente la cantidad de palabras en los lados izquierdo y derecho. (El nodo con el subíndice i en la matriz tiene un nodo hijo izquierdo con el subíndice i?2, un nodo hijo derecho con el subíndice i?2+1 y un subíndice i/2?)

Si ponemos El elemento recién insertado al final del montón, puedes ver esta imagen que hice, ¿no coincide con las características del montón? Por lo tanto, debemos ajustarlo para que vuelva a cumplir con las propiedades del montón. A este proceso lo llamamos heapify.

De hecho, hay dos formas de heapización: de abajo hacia arriba y de arriba hacia abajo. A continuación, comenzaré con el enfoque ascendente para heapify.

La amontonamiento es muy simple, simplemente compara e intercambia a lo largo del camino del nodo, hacia arriba o hacia abajo.

Colocamos el último nodo en la parte superior del montón y luego utilizamos el mismo método de comparación de nodos padre-hijo. Para aquellos nodos que no satisfacen la relación de tamaño entre los nodos padre e hijo, intercambie los dos nodos y repita el proceso hasta que se satisfaga la relación de tamaño entre los nodos padre e hijo. Este es un apilamiento de arriba hacia abajo.

La altura de un árbol binario completo con n nodos no excederá log2?n. El procedimiento del montón compara los intercambios a lo largo de las rutas de los nodos, por lo que la complejidad temporal del montón es proporcional a la altura del árbol, que es O (logn). La lógica principal de insertar datos y eliminar elementos en la parte superior del montón es la acumulación, por lo que la complejidad temporal de insertar elementos en el montón y eliminar elementos en la parte superior del montón es O (logn).

El algoritmo de clasificación que implementamos aquí con la ayuda de una estructura de datos como un montón se llama clasificación de montón. La complejidad temporal de este método de clasificación es muy estable, solo O (nlogn), y también es un algoritmo de clasificación in situ.

La matriz se procesa de atrás hacia adelante, con cada dato apilado de arriba a abajo.

Dado que los nodos hoja apilados hacia abajo solo pueden compararse entre sí, simplemente comenzamos con el último nodo que no es hoja y los apilamos en orden.

La complejidad temporal de construir el montón es O (n). Para obtener una derivación, consulte Geek Time: la belleza de las estructuras de datos y los algoritmos.

Una vez construido el montón, los datos de la matriz se han organizado de acuerdo con las características del gran montón. El primer elemento de la matriz es la parte superior del montón, que es el elemento más grande. Lo intercambiamos con el último elemento y el elemento más grande se coloca en la posición con n subíndice.

Este proceso es algo similar a la operación de "eliminación de la parte superior del montón" descrita anteriormente, es decir, eliminar el elemento superior del montón, colocar el elemento con n subíndice en la parte superior del montón y luego El apilamiento de los n?1 elementos restantes se reconstruye en un montón. Una vez completado el montón, colocamos el elemento en la parte superior del montón en la posición con el subíndice n? 1, y luego repetimos este proceso hasta que solo quede un elemento marcado con 1 en el montón y se complete la clasificación.

Todo el proceso de clasificación en montón requiere solo una pequeña cantidad de espacio de almacenamiento temporal, por lo que la clasificación en montón es un algoritmo de clasificación in situ. La clasificación del montón incluye dos operaciones: construcción del montón y clasificación. La complejidad temporal del proceso de construcción del montón es O (n) y la complejidad temporal del proceso de clasificación es O (nlogn). (nlog).

La clasificación del montón no es un algoritmo de clasificación estable porque durante el proceso de clasificación, hay una operación de intercambio del último nodo del montón con el nodo superior del montón, por lo que es posible cambiar el valor original. de datos con el mismo valor.

El montón es una estructura de datos muy importante en varias aplicaciones: cola de prioridad, Top K y mediana.

Supongamos que tenemos 100 archivos pequeños, cada archivo tiene un tamaño de 100 MB y cada archivo almacena una cadena ordenada. Queremos fusionar estos 100 archivos pequeños en un archivo grande y ordenado. Aquí es donde entra en juego la cola de prioridad.

Aquí se puede utilizar una cola o montón de prioridad. Colocamos las cadenas del archivo pequeño en la parte superior del montón pequeño. El elemento en la parte superior del montón, es decir, el elemento en la parte superior de la cola de prioridad, es la cadena más pequeña. Colocamos la cadena en un archivo grande y la eliminamos del montón. Luego, tomamos la siguiente cadena del archivo pequeño y la colocamos en el montón. En este proceso, los datos de cada uno de los 100 archivos pequeños se colocan uno por uno en el archivo grande.

Podemos utilizar la cola de prioridad para resolver este problema. Almacenamos tareas en una cola de prioridad según su tiempo de ejecución, y el encabezado de la cola (es decir, la parte superior del mini-montón) almacena la primera tarea ejecutada.

¿Cómo encontrar la parte superior de K big data en una matriz que contiene n datos? Podemos mantener un pequeño montón superior de tamaño K, iterar sobre la matriz en orden, luego obtener los datos de la matriz y compararlos con el elemento superior del montón. Si los datos son más grandes que el elemento superior del montón, eliminamos el elemento superior y lo insertamos en el montón; si los datos son más pequeños que el elemento superior del montón, lo ignoramos y continuamos atravesando la matriz. Si es menor que el elemento superior del montón, lo ignoramos y continuamos atravesando la matriz. Después de atravesar los datos de la matriz, los datos del montón son los primeros K big data.

Como sugiere el nombre, la mediana es el número que está en el medio.

Se utilizan dos montones: el montón superior grande y el montón superior pequeño. Los datos del montón máximo pequeño siempre son mayores que los datos del montón máximo grande.

Si los datos nuevos son menores o iguales que el elemento superior del montón grande superior, insertamos los datos nuevos en el montón grande superior; de lo contrario, insertamos los datos nuevos en el montón pequeño superior;

Es decir, si hay n datos, n es un número par y clasificamos de pequeño a grande, entonces los primeros 2n datos se almacenan en el montón superior grande y el último 2n datos se almacenan en el pequeño montón superior. Por lo tanto, el elemento superior del gran montón es la mediana que buscamos. Si n es un número impar, la situación es similar, 2n?+1 datos se almacenan en el montón superior, 2n?

Geek Time - La belleza de las estructuras de datos y los algoritmos - 28 | ordenar: ¿por qué la ordenación en montón no es tan buena como la ordenación rápida?