El montón en la gestión de la memoria se parece más a un grupo. Hayuna discusión en StackOverflow, no hablamos del detalle de esta diferencia.Sabes que estamos hablando del concepto de montón en algoritmo y estructura de datos es suficiente para nosotros.Todavía seguimos el estilo deIntroducción a los algoritmos.El montón es un árbol binario completo representado por una matriz.Un árbol binario es un tipo de árbol, cada nodo padre tiene como máximo dos hijos, los llamamos subárbol izquierdo y subárbol derecho.
Un árbol binario perfecto es un árbol binario cuando el recuento de capas es k, tiene 2k
-1 nodos.Como esto:Y podemos pensar que un árbol binario completo es un árbol binario perfecto con fugas o que no le faltan algunos nodos sino que debe llenar los nodos de arriba a abajo, de izquierda a derecha.
Significa que sólo pueden faltar algunos nodos de la derecha.Como esto:
Cuando usamos un montón para almacenar este árbol binario completo, podemos guardarlo como una matriz como esta: [A, B, C, D, E, F, G, H, I, J, K, L].Utilice este método de almacenamiento, descubriremos que el índice de la raíz de este árbol es 1.
Y el índice de cada nodo padre es el índice del nodo hijo dividido por 2. Y el índice del subnodo izquierdo es el índice de su nodo padre multiplicado por 2, el índice del subnodo derecho es su padre.El índice del nodo multiplica 2 y luego suma 1.
Entonces obtenemos la función para acceder a los nodos secundarios y principales.
Luego analizamos una estructura de datos, Max-Heap.Es un montón, cada padre más grande que sus hijos.Entonces sabemos que en una raíz Max-Heap está el número más grande.La imagen es un Max-Heap y su matriz correspondiente.
Puedes definir fácilmente un Min-Heap, no lo discutiremos ahora.
Si un nodo de unmontón máximomás pequeño que sus subnodos, viola la regla del montón máximo.Si sabemos que sus subnodos son max-heap válidos, podemos corregirlo mediante unmax-acumularoperación.Los pasos son comparar el valor de este nodo y sus hijos, quién es el más grande, si no es el nodo padre, intercambiamos el subnodo más grande con el nodo padre.Luego examinamos el subnodo, con sus hijos.Paso a paso, podemos asegurarnos de que después de la operación el montón máximo sea válido.
Hacemos una demostración en video, 4 es el nodo de error.
Este es el código._A es la matriz que almacena el montón y el índice -1 porque en Java el índice de la matriz comienza desde 0:
Para que se ejecute Max-Heapify, escribimos una función auxiliar de intercambio:
Entonces, ¿cómo podemos construir un Max-heap a partir de un árbol binario completo aleatorio?Supongamos que tenemos un montón como este:
Podemos comenzar desde el medio del montón (el quinto nodo) y volver a la raíz uno por uno para realizar la operación max-heapify.Cuando terminó, tenemos un montón máximo.Este es un vídeo de demostración para esto:
Código como este:
Cuando miramos detenidamente, descubriremos que max-heap no es una estructura de datos ordenada.Cada nodo principal es más grande que sus hijos, pero el subnodo izquierdo puede ser más grande y también más pequeño que el subnodo derecho.No podemos obtener fácilmente una matriz ordenada simplemente atravesando el árbol binario de ninguna manera.Entonces, ¿cómo usamos un montón para ordenar números?
Sabemos que la raíz siempre es la más grande.Entonces podemos intercambiar la raíz con el último nodo, luego eliminar el último nodo del montón y maximizar la raíz.Luego, el montón restante se convierte en un montón máximo válido, podemos hacer esto una y otra vez.Siempre ponemos el número más grande detrás, por lo que obtenemos una matriz ordenada.
Podemos comenzar desde este montón máximo para ordenar.
Y este es nuestro vídeo de demostración:
Código como este:
Y max-heap puede soportar una operaciónExtraerMax, devuelve la raíz, elimínala y reduce el montón.Podemos usarlo para obtener el número máximo o el k número más grande sin ordenarlo primero.Código como este:
Entonces podemos usar max-heap para ordenar números.O podemos usarlo para obtener el número máximo u obtener el k número más grande para pagar menos costo que ordenarlo.
Dirección de GitHubï¼https://github.com/tinyfool/leetcode/blob/master/src/CLRS/HeapSort.java
Problemas de LeetCode relacionados con el montón y la clasificación del montón:
