Continuamos sumergiéndonos en una variedad de montones.Hoy analizaremos un método de pedido elegante que utiliza montones especiales basados en los números de Leonardo.Muchos han escuchado sobre esta clasificación, pero pocas personas saben exactamente cómo funciona. Hoy veremos que no hay nada complicado en ello. El método fue inventado por el legendario Edsger Dijkstra. Además de los muchos logros más brillantes en la teoría de algoritmos, también es autor de una afirmación tan ingeniosa: “Los estudiantes que han estudiado previamente Básico, es casi imposible enseñar una buena programación. Como programadores potenciales, han sufrido una degradación mental irreversible ".
Espero que no sea una blasfemia que la animación del artículo se haya creado usando VBA :-)
EDISON.
, Android iOS.
! ;-)
La ordenación del montón en sí misma es muy buena, ya que su complejidad temporal es O ( n log n ) independientemente de los datos. Para no representar una matriz, la complejidad del montón nunca se degrada a O ( n 2 ) , lo que puede suceder, por ejemplo, con una ordenación rápida. La otra cara de la moneda es que no se puede acelerar la clasificación por un montón binario, tampoco se puede esperar complejidad O ( n ) (pero la misma clasificación rápida, bajo ciertas condiciones, puede alcanzar tales indicadores).En general, había una pregunta en la agenda: ¿es posible idear para que la complejidad temporal de la clasificación por un montón, por un lado, no sea inferior aO ( n log n ) , pero en un escenario favorable (en particular, si se procesa una matriz casi ordenada) aumenta a O ( n ) ?Este problema fue abordado personalmente por el propio Edsger Dijkstra, quien descubrió que sí, es posible.Se supone que aquellos que leen este artículo entienden cómo funciona la clasificación por montón en general, saben qué es el árbol de clasificación y por qué se necesita un tamizado. Si alguien tiene lagunas en este conocimiento, entonces antes de continuar leyendo, le recomiendo que lea el artículo anterior .¿Qué tiene de malo un montón binario?
Echemos un vistazo a cómo ordena el montón una matriz casi ordenada y veamos por qué este algoritmo no procesa esos datos entrantes más rápido.Haga clic en la animación para ir al artículo "Ordenar por una pirámide n".Lo primero que llama la atención es que, al tamizar, los máximos se empujan constantemente a la raíz del montón, que corresponde al primer elemento de la matriz. Si la matriz de entrada está casi ordenada, entonces para el algoritmo esto solo agregará un poco de trabajo. Los elementos más pequeños aún irán primero por el árbol, es decir. acercarse al final de la matriz, no a su comienzo.El segundo factor de desaceleración, que no es tan obvio, es que el montón binario estándar en sí mismo es siempre un árbol equilibrado. En el caso de los datos inicialmente ordenados, esto juega un papel negativo. Si hay datos aleatorios en la matriz original, se distribuyen uniformemente en un árbol equilibrado, y el cribado múltiple pasa por todas las ramas aproximadamente el mismo número de veces. Para datos casi ordenados, es más preferible un árbol desequilibrado; en este caso, los datos en esa parte de la matriz que corresponden a ramas más largas del árbol se procesarán con menos frecuencia que otros.Leonardo números
Para resolver ambos problemas, Dijkstra propuso usar montones binarios especiales basados en números de Leonardo.Los números de Leonardo son casi como los números de Fibonacci, pero solo mejores.Se da una serie recursiva de números de Leonardo:L 0 = 1L 1 = 1L n = L n - 1 + L n - 2 + 1Los primeros 20 números de Leonardo:1, 1, 3, 5, 9, 15, 25, 41, 67 , 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529Absolutamente cualquier número entero puede representarse como la suma de los números de Leonardo que tienen diferentes números de serie.Esto es muy útil en nuestro caso. Matriz de nlos elementos no siempre se pueden representar como un solo montón de Leonardo (si n no es un número Leonardo). Pero entonces, cualquier matriz siempre se puede dividir en varias submatrices que corresponderán a diferentes números de Leonardo, es decir. ser montones de diferente orden.Aquí hay un ejemplo de una matriz del elemento 21, que consta de tres montones de Leonard. En cada uno de los montones, el número de nodos corresponde a cualquier número de Leonardo.Puntos importantes a saber:- Cada pila de Leonardov es un árbol binario desequilibrado.
- La raíz de cada montón es el último (y no el primero, como en un montón binario regular) del subarreglo correspondiente.
- Cualquier nodo con todos sus descendientes es también un montón de Leonard de menor orden.
Construye y desmonta montones
En la fórmula de recurrencia para los números de Leonardo,L n = L n - 1 + L n - 2 + 1 estámuy satisfecho con la unidad al final.Y es por eso. Supongamos que tenemos dos submatrices adyacentes en la matriz que corresponden a montones construidos en dos números Leonardo adyacentes. Usando el elemento inmediatamente después de estas submatrices, estas submatrices se pueden combinar en un montón común, que corresponde al siguiente número de Leonard.Al revisar los elementos en la matriz, construimos un montón de montones de Leonard. Si usa el elemento, puede combinar los dos montones anteriores (esto es posible si y solo si los dos montones anteriores corresponden a dos números Leonardo consecutivos), entonces combine. Si la combinación no es posible (los dos montones anteriores no corresponden a dos números Leonardo consecutivos), entonces el elemento actual simplemente forma un nuevo montón de un elemento correspondiente al primer (o segundo, si el primero se usa antes) número Leonardo.En la segunda etapa del algoritmo, se produce el proceso inverso: analizamos los montones. Si eliminamos la raíz en el montón, obtenemos dos montones más pequeños correspondientes a los dos números anteriores de Leonardo. Esto se puede hacer porque:L n - 1 = L n - 1+ L n - 2En los números de Fibonacci no existe una unidad tan útil, por lo tanto, no utilizamos el montón de Fibonacci.Clasificación suave :: Smoothsort
El algoritmo final:- I. Cree un montón de montones de Leonard de la matriz, cada uno de los cuales es un árbol de clasificación.
- I.1 Iterar sobre los elementos de la matriz de izquierda a derecha.
- II.1. Verificamos si al usar el elemento actual es posible combinar los dos montones más a la izquierda en el montón de montones de Leonard existente:
- II.1.a. En caso afirmativo, combinamos los dos montones más a la izquierda en uno, el elemento actual se convierte en la raíz de este montón, hacemos un tamiz para el montón combinado.
- II.1.b. De lo contrario, agregue el elemento actual como un nuevo montón (que consta de un nodo hasta ahora) al montón existente de montones de Leonard.
- II. , :
- II.1. . , .
- II.2. ( ) ( ).
- II.3. , . .
- II.4. ( ), .
- II.5. Después de mover el elemento máximo al final, la parte ordenada de la matriz aumentó y la parte no ordenada disminuyó. Repita los pasos II.1-II.4 para la parte no ordenada restante de la matriz.
Ejemplo de implementación de Python
import random
def smoothsort(lst):
leo_nums = leonardo_numbers(len(lst))
heap = []
for i in range(len(lst)):
if len(heap) >= 2 and heap[-2] == heap[-1] + 1:
heap.pop()
heap[-1] += 1
else:
if len(heap) >= 1 and heap[-1] == 1:
heap.append(0)
else:
heap.append(1)
restore_heap(lst, i, heap, leo_nums)
for i in reversed(range(len(lst))):
if heap[-1] < 2:
heap.pop()
else:
k = heap.pop()
t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
heap.append(k_l)
restore_heap(lst, t_l, heap, leo_nums)
heap.append(k_r)
restore_heap(lst, t_r, heap, leo_nums)
def leonardo_numbers(hi):
a, b = 1, 1
numbers = []
while a <= hi:
numbers.append(a)
a, b = b, a + b + 1
return numbers
def restore_heap(lst, i, heap, leo_nums):
current = len(heap) - 1
k = heap[current]
while current > 0:
j = i - leo_nums[k]
if (lst[j] > lst[i] and
(k < 2 or lst[j] > lst[i-1] and lst[j] > lst[i-2])):
lst[i], lst[j] = lst[j], lst[i]
i = j
current -= 1
k = heap[current]
else:
break
while k >= 2:
t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
if lst[i] < lst[t_r] or lst[i] < lst[t_l]:
if lst[t_r] > lst[t_l]:
lst[i], lst[t_r] = lst[t_r], lst[i]
i, k = t_r, k_r
else:
lst[i], lst[t_l] = lst[t_l], lst[i]
i, k = t_l, k_l
else:
break
def get_child_trees(i, k, leo_nums):
t_r, k_r = i - 1, k - 2
t_l, k_l = t_r - leo_nums[k_r], k - 1
return t_r, k_r, t_l, k_l
def main(n):
lst = list(range(n))
random.shuffle(lst)
print(lst)
smoothsort(lst)
print(lst)
Complejidad de tiempo
Si tomamos una matriz casi ordenada como entrada, entonces la visualización muestra por qué dicha matriz se procesa mucho más rápido.Los ahorros se producen solo debido al tamizado. En datos casi ordenados, el tamizado se hunde poco profundo en el árbol, incluso después de que los montones se disuelven gradualmente en la segunda etapa. En los datos inicialmente aleatorios, el cribado es más costoso, ya que a menudo cae en su montón hasta el último nivel.Vamos a estimar la complejidad del tiempo total.En la primera etapa, iteramos sobre n elementos, agregándolos a los montones que ya existen a la izquierda. Agregar al montón en sí mismo se omite en O (1), pero luego para el montón necesita hacer un tamiz. En los datos ordenados, un tamizado superficial a menudo cuesta O (1) para un elemento agregado al montón. En datos desordenados, el tamizado para cada adición se calcula en O (log n ), ya que como resultado de la aleatoriedad, el cribado tiene que pasar a través de los niveles de los árboles a menudo hasta el fondo.Por lo tanto, en la primera etapa, la mejor complejidad temporal es:para datos casi ordenados - O ( n ),para datos aleatorios - O ( n log n ).Para la segunda etapa, la situación es similar. Al intercambiar el siguiente máximo, nuevamente necesita tamizar el montón en la raíz de la que era. Y las métricas de selección de datos ordenados y desordenados serán diferentes.En la segunda etapa, la mejor complejidad temporal es la misma que en la primera:para datos casi ordenados - O ( n ),para datos aleatorios - O ( n log n ).Agregar complejidad de tiempo para la primera y segunda etapa:para datos casi ordenados - O (2 n ) = O ( n ),para datos aleatorios - O (2 n log n ) = O ( n log n ).En general, la complejidad de tiempo peor y promedio para una ordenación suave es O ( n log n ).Dijkstra en sus cálculos (con los que no te aburriré) demostró que la mejor complejidad tiende suavemente a O ( n ) que la más ordenada de los datos entrantes. De ahí el nombre: ordenación suave.Complejidad de memoria extra
Para descomponer los datos en un montón de montones de Leonard, solo necesita recordar exactamente qué números de Leonardo están involucrados en cada paso. Conociendo estos números, los montones mismos están alineados algorítmicamente. Esta serie de números crece muy rápidamente, por lo que incluso para matrices grandes necesitará un conjunto muy pequeño de números de Leonard.Clasificación del montón binomial :: Clasificación del montón binomial
Hay una estructura de árbol, muy similar a la que resolvimos: un montón binomial . Esto también es un montón de montones de diferentes tamaños, en cada uno de los cuales el número de nodos es una potencia de dos. Cualquier conjunto de cualquier número de elementos puede expandirse en este montón, ya que cualquier número natural se descompone en la suma de dos de diferentes grados.En principio, puede hacer una ordenación suave basada en binomios:¿Funcionará más rápido? Apenas. El montón binomial no es binario, y en el último artículo descubrimos que aumentar el número de descendientes no acelera, sino que ralentiza la pantalla . Además, puede observar que el montón binomial tiene ramas más largas, por lo que las regiones ordenadas vecinas de la matriz serán un poco más lentas para conectarse entre sí.No se sabe si el montón binomial de Dijkstra se consideró generalmente como una posible base para su algoritmo. Sea como fuere, el montón de Leonardov es probablemente más óptimo.Trailer de la próxima serie
Sin embargo, incluso si una pila binomial no es la mejor opción para una clasificación suave, no debe descartarla por completo.Si el árbol binomial está ligeramente modificado y se usan ideas completamente diferentes (muy audaces) para rodearlo, entonces obtenemos un algoritmo original y efectivo que tiene sus propias ventajas. ¿De qué vamos a hablar la próxima vez?Haga clic en la animación para ir al artículo con la siguiente clasificación por montón.Referencias
El número liso / liso de Leonardo , montón binomial / montón binomialArtículos de la serie:
La ordenación suave de hoy se ha agregado a la aplicación AlgoLab. Además de una bonificación, y ordenar con una pila binomial. Entonces, ¿quién quiere manejar personalmente los datos en los montones de montón? Actualice el archivo Excel con macros.