La clasificación en un montón (también es una clasificación piramidal) en Habré ya se ha recordado con una buena palabra más de una o dos veces, pero esta siempre ha sido una información bastante conocida. Todos conocen el montón binario habitual, pero la teoría de los algoritmos también tiene: unn-montón; un montón de montones basados en los números de Leonardo; Deramida (un híbrido de montón y árbol de búsqueda binario); mini-pila de torneo; montón espejo (inverso); pila débil El montón de Jung; pila binomial; y Dios sabe qué otros montones ...Y los representantes más inteligentes de la informática en diferentes años propusieron sus algoritmos de clasificación utilizando estas estructuras piramidales. A quién le importa lo que hicieron: para aquellos estamos comenzando una pequeña serie de artículos dedicados a la clasificación utilizando estas estructuras. El mundo de los montones es diverso. Espero que te interese.
Este artículo fue escrito con el apoyo de EDISON.
Nos dedicamos al desarrollo de aplicaciones móviles y brindamos servicios de prueba de software .
¡Nos encanta la teoría de los algoritmos! ;-)
Existe una clase de algoritmos de este tipo: ordenar por elección. La idea general es que la parte desordenada de la matriz se reduce debido al hecho de que busca los elementos máximos que se reordenan en un área ordenada creciente.Ordenar la elección habitual es la fuerza bruta. Si, en busca de máximos, es simple recorrer linealmente la matriz, entonces la complejidad temporal de dicho algoritmo no puede exceder O ( n 2 ).Un manojo
La forma más eficiente de trabajar con los máximos en la matriz es organizar los datos en una estructura de árbol especial, conocida como montón . Este es un árbol en el que todos los nodos principales no son menos que los nodos descendientes.Otros nombres del montón: la pirámide , el árbol de clasificación .Veamos cómo puede ser fácil y casi gratis presentar una matriz en forma de árbol.Tome el primer elemento de la matriz y considere que esta es la raíz del árbol, un nodo del primer nivel. Los siguientes 2 elementos son nodos del segundo nivel, los descendientes derecho e izquierdo del elemento raíz. Los siguientes 4 elementos son nodos del tercer nivel, los descendientes derecho / izquierdo del segundo / tercer elemento de la matriz. Los siguientes 8 elementos son nodos del 4 ° nivel, descendientes de elementos del 3 ° nivel. Etc. En esta imagen, los nodos del árbol binario están claramente ubicados estrictamente debajo de los elementos correspondientes en la matriz:Sin embargo, los árboles en los diagramas se representan con mayor frecuencia en dicho escaneo:Si observa este ángulo, está claro por qué la clasificación por grupos se denomina clasificación piramidal. Aunque, esto es casi lo mismo que si llamas a un elefante de ajedrez un oficial, una torre una tura y una reina una reina.Los índices para los descendientes del i -ésimo elemento se determinan por elemental (si el índice del primer elemento de la matriz se considera igual a 0, como es habitual en la mayoría de los lenguajes de programación):descendiente izquierdo de 2 × i + 1,el hijo derecho: 2 × i + 2(estoy en los gráficos y en las animaciones, tradicionalmente, los índices de matrices comienzan con 1, donde las fórmulas son ligeramente diferentes: hijo izquierdo: 2 × iy niño derecho: 2 × i + 1, pero estos ya son pequeños matices aritméticos).Si la descendencia resultante de estas fórmulas los índices van más allá de la matriz, significa que el i -ésimo elemento no tiene hijos. También puede suceder que el i -ésimo elemento sea un descendiente izquierdo (cae en el último elemento de la matriz en el que hay un número impar de elementos), pero no hay ningún derecho.Por lo tanto, cualquier matriz se puede representar fácilmente en forma de árbol, sin embargo, esto aún no es un grupo, porque, en la matriz, algunos elementos descendientes pueden ser más grandes que sus elementos principales.Para que nuestro árbol, creado sobre la base de la matriz, se convierta en un montón, debe ser cribado correctamente.Cernido
El alma de clasificar un grupo es tamizar.El cribado de un elemento es que si es más pequeño que los descendientes combinados en una cadena inextricable, entonces este elemento debe moverse lo más bajo posible, y los descendientes más grandes deben elevarse 1 nivel hacia arriba.La imagen muestra la ruta de tamizado para el artículo. El color azul indica el elemento para el que se realiza el cribado. Verde: descendientes más grandes en la rama. Se elevarán un nivel más arriba, porque son más grandes que el nudo azul para el que está hecha la pantalla. El elemento mismo del nodo azul superior se moverá al lugar del descendiente más bajo de la cadena verde.Se necesita un tamiz para hacer un árbol de clasificación de un árbol ordinario y para soportar aún más el árbol en este estado (clasificación).En esta imagen, los elementos de la matriz se redistribuyen de modo que ya se presentan en un montón. Aunque la matriz se descompone en un árbol de clasificación, aún no se ha ordenado (ya sea ascendente o descendente), aunque todos los descendientes en el árbol son más pequeños que sus nodos principales. Pero el elemento más máximo en el árbol de clasificación siempre está en la raíz principal, lo cual es muy importante.Heap Sort :: Heapsort
El algoritmo es realmente simple:- Etapa 1. Formamos un árbol de clasificación de toda la matriz. Para hacer esto, pasamos de derecha a izquierda los elementos (del último al primero) y si el elemento tiene descendientes, entonces lo separamos.
- 2. . , . ( ) . , .. . , — . , .
Código de Python para una implementación clásica de ordenación piramidal:
def HeapSort(data):
for start in range((len(data) - 2) / 2, -1, -1):
HeapSift(data, start, len(data) - 1)
for end in range(len(data) - 1, 0, -1):
data[end], data[0] = data[0], data[end]
HeapSift(data, 0, end - 1)
return data
def HeapSift(data, start, end):
root = start
while True:
child = root * 2 + 1
if child > end: break
if child + 1 <= end and data[child] < data[child + 1]:
child += 1
if data[root] < data[child]:
data[root], data[child] = data[child], data[root]
root = child
else:
break
Complejidad Algoritmo
Por qué un montón simple es bueno: no necesita almacenarse por separado, a diferencia de otros tipos de árboles (por ejemplo, se debe crear un árbol de búsqueda binario basado en una matriz antes de usarlo). Cualquier matriz ya es un árbol en el que, sobre la marcha, puede identificar inmediatamente a los padres y descendientes. La complejidad de la memoria adicional es O ( 1 ), todo sucede de inmediato.En cuanto a la complejidad del tiempo, depende del tamizado. Un solo cribado se omite en O (log n ) . Primero, seleccionamos n elementos para construir el montón inicial a partir de la matriz; este paso requiere O ( n log n ) . En la segunda etapa, cuando sacamos nlos máximos actuales del montón, hacemos un solo cribado para la parte sin clasificar restante, es decir esta etapa también nos cuesta O ( n log n ) .Complejidad de tiempo total: O ( n log n ) + O ( n log n ) = O ( n log n ).Además, la clasificación piramidal no tiene casos degenerados ni mejores. Cualquier matriz se procesará a una velocidad decente, pero no habrá degradación ni registros.La clasificación del montón en promedio es un poco más lenta que la clasificación rápida. Pero para el ordenamiento rápido, puede elegir una matriz asesina en la que se cuelga la computadora, pero para el ordenamiento dinámico: no.:: Ternary heapsort
Veamos el montón ternario. No lo creerá del binario, solo difiere en que los nodos principales tienen un máximo de no dos, sino tres descendientes. En el montón ternario para el i -ésimo elemento codifica tres descendientes calculados de manera similar (si el índice del primer elemento = 0):El descendiente izquierdo 3 × i + 1El descendiente medio 3 × i + 2el descendiente derecho 3 × i + 3(Si los índices comienzan con 1, como en las animaciones de este artículo, luego en estas fórmulas solo necesita restar uno).Proceso de clasificación:Por un lado, el número de niveles en el árbol disminuye notablemente en comparación con el montón binario, lo que significa que, en promedio, habrá menos intercambios durante el cribado. Por otro lado, para encontrar el descendiente mínimo, se necesitarán más comparaciones, porque los descendientes ahora no son dos, sino tres cada uno. En general, en términos de complejidad temporal: en algún lugar que encontramos, en algún lugar que perdemos, pero en general lo mismo. Los datos en el montón ternario se ordenan un poco más rápido que en el binario, pero esta aceleración es muy pequeña. En todas las variaciones de la ordenación piramidal, los desarrolladores de los algoritmos prefieren tomar la opción binaria, porque el ternario supuestamente es más difícil de implementar (aunque es "más difícil" agregar un par o tres líneas adicionales al algoritmo), y la ganancia de velocidad es mínima.Ordenar por n-heap heap :: N-narny heapsort
Por supuesto, no puede detenerse allí y adaptar la clasificación por grupos para cualquier cantidad de descendientes. ¿Quizás si continúa aumentando el número de descendientes, puede aumentar significativamente la velocidad del proceso?Para el i -ésimo elemento de los índices de matriz (si el recuento de cero), sus N descendientes calcula muy simple:primero descendiente: N × i + 1segundo descendiente: N × i + 2tercera descendiente: N × i + 3...Enésimo descendiente: N × i + NCódigo de Python para ordenar por un N-montón:
def NHeapSort(data):
n = 3
for start in range(len(data), -1, -1):
NHeapSift(data, n, start, len(data) - 1)
for end in range(len(data) - 1, 0, -1):
data[end], data[0] = data[0], data[end]
NHeapSift(data, n, 0, end - 1)
return data
def NHeapSift(data, n, start, end):
root = start
while True:
child = root * n + 1
if child > end:
break
max = child
for k in range(2, n + 1):
current = root * n + k
if current > end:
break
if data[current] > data[max]:
max = current
if data[root] < data[max]:
data[root], data[max] = data[max], data[root]
root = max
else:
break
Sin embargo, más no significa mejor. Si lleva la situación al límite y toma N descendientes para una matriz de N elementos, entonces la clasificación por grupos se degrada a la clasificación por la elección habitual. Además, también será una versión peor de la clasificación por selección, porque se realizarán gestos sin sentido: el cribado primero colocará el máximo en primer lugar en la matriz, y luego enviará el máximo al final (en el orden de selección, el máximo se envía al final inmediatamente).Si el montón ternario supera mínimamente el binario, entonces el cuádruple ya está perdiendo. Encontrar el descendiente máximo entre varios se vuelve demasiado costoso.Trailer de la próxima serie
Entonces, la principal desventaja del binario / ternario / n-montón es que la incapacidad para saltar en su complejidad es mayor que O ( n log n ) . La forma de salir del punto muerto es utilizar variedades de montón más sofisticadas en la clasificación. En una semana nos familiarizaremos con lo que Edsger Dijkstra piensa sobre esto.Haga clic en la animación para ir al artículo con la siguiente clasificación por gruposReferencias
Montón / PirámideArtículos de la serie:
La aplicación AlgoLab agregó la clasificación por n-montón. Para seleccionar el número de descendientes, en el comentario en la celda de este tipo, debe especificar un número para n. El rango de valores posibles es de 2 a 5 (no tiene más sentido, porque para n> = 6, la animación con tres niveles de anidamiento a una escala normal no se garantiza que quepa en la pantalla).