1. Tengo que hablar de árboles binarios
Para comprender el montón, primero debe comprender el árbol binario. En la informática, un árbol binario es una estructura de árbol con la mayoría de los dos subárboles por nodo. Por lo general, los subárboles se llaman "subárbol izquierdo" y "subárbol derecho". Los árboles binarios a menudo se usan para implementar árboles de búsqueda binarios y montones binarios.
Cada nodo de un árbol binario tiene como máximo dos subárboles (nodos con grados mayores que 2). Los subárboles de un árbol binario se pueden dividir en izquierda y derecha, y el orden no se puede revertir. La capa i -th del árbol binario tiene como máximo el nodo 2i - 1; El árbol binario con una profundidad de K tiene como máximo el nodo 2k - 1; Para cualquier árbol binario t, si el número de nodos terminales es N0 y el número de nodos con un grado de 2 es N2, N0 = N2 + 1.
Hay tres diferencias principales entre un árbol y un árbol binario:
El número de nodos en el árbol es al menos 1, mientras que el número de nodos en el árbol binario puede ser 0.
No hay límite en el máximo grado de nodos en el árbol, mientras que el grado máximo de nodos en el árbol binario es 2
No hay diferencia entre la izquierda y la derecha en los nodos de un árbol, mientras que no hay diferencia entre la izquierda y la derecha en los nodos de un árbol binario.
Los árboles binarios se dividen en árboles binarios completos y árboles binarios completos.
Árbol binario completo: un árbol con una profundidad de k y tiene 2k - 1 nodo se llama árbol binario completo
(Árbol binario completo con profundidad 3)
Árbol binario completo: un árbol binario con n nodos con profundidad k. Se llama un árbol binario completo si y solo si cada uno de sus nodos corresponde a un nodo con números de secuencia de 1 a n en un árbol binario completo con profundidad k.
(Árbol binario completo con profundidad 3)
2. ¿Qué es un montón?
Un montón (montón binario) puede considerarse como un árbol binario completo. Una propiedad "excelente" de un árbol binario completo es que, excepto la capa inferior, cada capa está llena, lo que permite que el montón se represente en una matriz (los árboles binarios generales ordinarios generalmente se representan mediante listas vinculadas como contenedores básicos), y cada nodo corresponde a un elemento en la matriz.
La siguiente figura muestra la relación entre un montón y una matriz
(La relación entre el montón y la matriz)
Para el subíndice I de un nodo, se puede calcular fácilmente para el subíndice del nodo principal y el nodo secundario de este nodo:
Padre (i) = piso (i/2), el subíndice del nodo principal de i
Izquierda (i) = 2i, el subíndice del nodo infantil izquierdo de i
Derecho (i) = 2i + 1, el subíndice de nodo infantil correcto de i
Generalmente hay dos tipos de montones binarios: el montón más grande y el montón más pequeño.
Montón máximo:
El valor máximo del elemento en el montón máximo aparece en el nodo raíz (superior del montón)
El valor del elemento de cada nodo principal en el montón es mayor o igual que su nodo hijo (si existe)
(Montón máximo)
Montón mínimo:
El valor mínimo del elemento en el montón mínimo aparece en el nodo raíz (superior del montón)
El valor del elemento de cada nodo principal en el montón es menor o igual a su nodo hijo (si existe)
(Pila mínima)
3. Principio de clasificación de montón
La clasificación del montón es eliminar el número máximo en la parte superior del montón máximo, continúe ajustando el montón restante al montón máximo y elimine el número máximo en la parte superior del montón nuevamente. Este proceso continúa hasta que solo haya un número restante. Defina las siguientes operaciones en el montón:
Max-Heapifify: ajuste el nodo final del montón para que el nodo secundario sea siempre más pequeño que el nodo principal
Cree un montón máximo (compilación-max-heap): reordene todos los datos del montón para que sea el montón máximo
Herman-sorte: retire el nodo raíz de los primeros datos y realice una operación recursiva del ajuste máximo del montón
Antes de continuar con la siguiente discusión, un problema que debe tenerse en cuenta es: las matrices están basadas en cero, lo que significa que nuestro modelo de estructura de datos Heap cambiará.
(Basado en cero)
En consecuencia, varias fórmulas de cálculo también deben ajustarse en consecuencia:
Padre (i) = piso ((I-1)/2), el subíndice de nodo principal de i
Izquierda (i) = 2i + 1, el subíndice del nodo infantil izquierdo de i
Derecho (i) = 2 (i + 1), el subíndice de nodo infantil correcto de i
La función del ajuste de montón máximo (maxheapify) es mantener las propiedades del montón más grande y es la subrutina central para crear el montón más grande. El proceso de operación se muestra en la figura:
(Max-Heapify)
Dado que el montón todavía viola la naturaleza del montón después de un ajuste, se requieren pruebas recursivas para que todo el montón satisfaga la naturaleza del montón. Se puede expresar en JavaScript de la siguiente manera:
/** * Compruebe desde el índice y mantenga las propiedades máximas del montón * * @array * * El índice inicial de @Index check * * @Heapsize tamaño de montón * **/function maxHeapifify (array, índice, hedapsize) {var imax = index, ileT = 2 * index + 1, iright = 2 * (índice + 1); if (ileft <thedepsize && array [index] <array [ileft]) {imax = ileft; } if (iright <Hepsize && Array [IMAX] <Array [iright]) {IMAX = iright; } if (imax! = index) {swap (array, imax, index); maxHeapify (matriz, IMAX, Heepsize); // ajuste recursivo}} swap de función (array, i, j) {var temp = array [i]; matriz [i] = array [j]; Array [j] = temp;}En términos generales, la recursión se usa principalmente en el método de división y tratamiento, y no hay necesidad de división y tratamiento aquí. Además, las llamadas recursivas requieren prensado/claro de pila, lo que tiene una ligera desventaja en el rendimiento en comparación con la iteración. Por supuesto, esto puede ignorarse de acuerdo con la regla 20/80. Pero si crees que usar la recursión te hará sentir incómodo, también puedes usar la iteración, como la siguiente:
/** * Compruebe desde el índice y mantenga las propiedades máximas del montón * * @array * * El índice inicial de @Index check * * @Heapsize Size * **/function maxHeapifify (matriz, índice, tedesize) {var imax, ileft, iright; while (true) {imax = index; Ileft = 2 * índice + 1; iright = 2 * (índice + 1); if (ileft <thedepsize && array [index] <array [ileft]) {imax = ileft; } if (iright <Hepsize && Array [IMAX] <Array [iright]) {IMAX = iright; } if (imax! = index) {swap (array, imax, index); índice = imax; } else {break; }}} function swap (array, i, j) {var temp = array [i]; matriz [i] = array [j]; Array [j] = temp;}El propósito de crear un montón máximo (compilación-max-heap) es transformar una matriz en un montón máximo, aceptando dos parámetros de matriz y tamaño de montón. Build-Max-Heap llamará a Max-Heapifify de abajo hacia arriba para transformar la matriz y construir el montón máximo. Debido a que Max-Heapifify puede garantizar que los nodos después de la suscripción, cumplan con las propiedades del montón más grande, la llamada de abajo hacia arriba a Max-Heapify puede mantener esta propiedad durante el proceso de transformación. Si el elemento de número de montón máximo es N, entonces Build-Max-HeAP llama a Max-Heapify en secuencia de Parent (N). El proceso es el siguiente:
La descripción es la siguiente en JavaScript:
función buildmaxHeap (array, Heepsize) {var i, iParent = math.floor ((HeepSize - 1) / 2); para (i = iParent; i> = 0; i--) {maxHeapify (matriz, i, tesepsize); }}Heap-Sort es el algoritmo de interfaz para la clasificación de almacenamiento de montón. El montón de clasificación primero llama a Built-Max-HeAP para transformar la matriz en el montón máximo, luego intercambia los elementos superior e inferior del montón, luego se eleva la parte inferior y finalmente llama a Max-Heapify para mantener las propiedades máximas del montón. Dado que el elemento superior del montón debe ser el elemento más grande en el montón, después de una operación, el elemento más grande presente en el montón se separa del montón del montón, y después de repetirse N-1 veces, la matriz está dispuesta. Todo el proceso es el siguiente:
La descripción es la siguiente en JavaScript:
function HeapSort (Array, HePsize) {BuildMaxHeap (Array, HePsize); para (int i = HeepSize-1; i> 0; i--) {swap (matriz, 0, i); maxHeapify (matriz, 0, i); }}4. Implementación del idioma de JavaScript
Finalmente, organice lo anterior en el código JavaScript completo de la siguiente manera:
function HeApSort (array) {function swap (array, i, j) {var temp = array [i]; matriz [i] = array [j]; matriz [j] = temp; } function maxHeApify (array, index, Heepsize) {var imax, ileft, iright; while (true) {imax = index; Ileft = 2 * índice + 1; iright = 2 * (índice + 1); if (ileft <thedepsize && array [index] <array [ileft]) {imax = ileft; } if (iright <Hepsize && Array [IMAX] <Array [iright]) {IMAX = iright; } if (imax! = index) {swap (array, imax, index); índice = imax; } else {break; }}} function buildmaxHeap (array) {var i, iParent = math.floor (array.length / 2) - 1; for (i = iParent; i> = 0; i--) {maxHeapify (array, i, array.length); }} Función Sort (Array) {BuildMaxHeap (Array); for (var i = array.length-1; i> 0; i--) {swap (matriz, 0, i); maxHeapify (matriz, 0, i); } matriz de retorno; } sort de retorno (matriz);}5. Aplicación del algoritmo de clasificación de montón
(1) rendimiento/complejidad del algoritmo
La complejidad del tiempo de la clasificación del montón es muy estable (podemos ver que no es sensible a los datos de entrada), y es la complejidad O (nn), el mejor caso es el mismo que el peor de los casos.
Sin embargo, su complejidad espacial varía según la implementación. Lo anterior discute dos complejidades comunes: O (N) y O (1). Basado en el principio de ahorro de espacio, recomiendo el método de complejidad O (1).
(2) Estabilidad del algoritmo
Hay una gran cantidad de procesos de filtrado y móvil en la clasificación de almacenamiento de montón, que pertenece a un algoritmo de clasificación inestable.
(3) Algoritmo escenario aplicable
La clasificación del montón incurrirá en una sobrecarga relativamente grande en el proceso de construir el montón y ajustar el montón, y no es aplicable cuando hay pocos elementos. Sin embargo, cuando hay muchos elementos, sigue siendo una buena opción. Especialmente al resolver problemas como "el número de n top n grande", es casi el algoritmo preferido.