Continuamos a mergulhar em uma variedade de montões.Hoje, analisaremos um método de pedido elegante que usa pilhas especiais com base nos números de Leonardo.Muitos já ouviram falar dessa classificação, mas poucas pessoas sabem exatamente como ela funciona. Hoje veremos que não há nada complicado. O método foi inventado pelo lendário Edsger Dijkstra. Além das muitas conquistas mais brilhantes da teoria dos algoritmos, ele também é o autor de uma declaração tão espirituosa: “Os alunos que estudaram o básico anteriormente, é quase impossível ensinar boa programação. Como programadores em potencial, eles sofreram degradação mental irreversível. ”
Espero que não seja blasfêmia que a animação no artigo tenha sido criada usando o VBA :-)
EDISON.
, Android iOS.
! ;-)
A classificação de heap em si é muito boa, pois sua complexidade de tempo é O ( n log n ), independentemente dos dados. Para não representar uma matriz, a complexidade do heapsort nunca diminui para O ( n 2 ) , o que pode acontecer, por exemplo, com uma classificação rápida. O outro lado da moeda é que a classificação por uma pilha binária não pode ser acelerada, O ( n ) complexidade também não pode ser esperada (mas a mesma classificação rápida, sob certas condições, pode alcançar esses indicadores).Em geral, havia uma pergunta na agenda: é possível inventar para que a complexidade do tempo de classificação por um monte, por um lado, não seja menor queO ( n log n ) , mas em um cenário favorável (em particular, se uma matriz quase classificada for processada) aumentada para O ( n ) ?Esse problema foi tratado pessoalmente pelo próprio Edsger Dijkstra, que descobriu que sim, é possível.Supõe-se que aqueles que lêem este artigo entendam como a classificação por heap funciona em geral, eles sabem o que é a árvore de classificação e por que uma peneiração é necessária. Se alguém tiver lacunas nesse conhecimento, antes de continuar lendo, recomendo que você leia o artigo anterior .O que há de errado com uma pilha binária
Vamos dar uma olhada em como o heapsort classifica uma matriz quase ordenada e ver por que esse algoritmo não processa esses dados recebidos mais rapidamente.Clique na animação para ir para o artigo “Classificando pela pirâmide-n.”A primeira coisa que chama sua atenção é que, ao peneirar, os máximos são constantemente empurrados para a raiz da pilha, que corresponde ao primeiro elemento da matriz. Se a matriz de entrada estiver quase ordenada, para o algoritmo isso adicionará apenas um pouco de trabalho. Os elementos menores ainda irão descer pela árvore, ou seja, aproxime-se do final da matriz, não do início.O segundo fator de lentidão, que não é tão óbvio, é que o heap binário padrão em si é sempre uma árvore equilibrada. No caso de dados solicitados inicialmente, isso desempenha um papel negativo. Se houver dados aleatórios na matriz original, eles serão distribuídos uniformemente em uma árvore balanceada e a peneiração múltipla será realizada em todos os ramos aproximadamente o mesmo número de vezes. Para dados quase ordenados, uma árvore desequilibrada é mais preferível - nesse caso, os dados daquela parte da matriz que correspondem a ramificações mais longas da árvore serão processados com menos frequência do que outros.Números Leonardo
Para resolver os dois problemas, Dijkstra propôs o uso de pilhas binárias especiais baseadas nos números de Leonardo.Os números de Leonardo são quase como os de Fibonacci, mas apenas melhores.Uma série de números de Leonardo é dada recursivamente:L 0 = 1L 1 = 1L n = L n - 1 + L n - 2 + 1Os primeiros 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 qualquer número inteiro pode ser representado como a soma dos números de Leonardo com números de série diferentes.Isso é muito útil no nosso caso. Matriz de nos elementos nem sempre podem ser representados como um único monte de Leonardo (se n não for um número de Leonardo). Mas então, qualquer matriz pode sempre ser dividida em vários sub-arranjos que corresponderão a diferentes números de Leonardo, ou seja, ser pilhas de ordem diferente.Aqui está um exemplo de uma matriz do 21º elemento, consistindo em três pilhas de Leonard. Em cada um dos montões, o número de nós corresponde a qualquer número de Leonardo.Pontos importantes a saber:- Cada pilha de Leonardov é uma árvore binária desequilibrada.
- A raiz de cada pilha é o último (e não o primeiro, como em uma pilha binária normal) do subarray correspondente.
- Qualquer nó com todos os seus descendentes também é um monte Leonard de uma ordem menor.
Construir e desmontar montões
Na fórmula de recorrência para números de Leonardo,L n = L n - 1 + L n - 2 + 1 estámuito satisfeito com a unidade no final.E é por causa disso. Suponha que tenhamos duas sub-matrizes adjacentes na matriz que correspondam às pilhas construídas em dois números Leonardo adjacentes. Usando o elemento imediatamente após essas sub-matrizes, essas sub-matrizes podem ser combinadas em um heap comum, que corresponde ao próximo número de Leonard.Examinando os elementos da matriz, construímos um monte de pilhas de Leonard. Se você estiver usando o elemento, poderá combinar os dois montões anteriores (isso é possível se e somente se os dois montantes anteriores corresponderem a dois números consecutivos de Leonardo), depois combine. Se a combinação não for possível (os dois heaps anteriores não correspondem a dois números consecutivos de Leonardo), o elemento atual simplesmente formará uma nova pilha de um elemento correspondente ao primeiro (ou segundo, se o primeiro for utilizado antes) número Leonardo.No segundo estágio do algoritmo, ocorre o processo inverso - analisamos os montões. Se removermos a raiz da pilha, obteremos duas pilhas menores correspondentes aos dois números anteriores de Leonardo. Isso pode ser feito porque:L n - 1 = L n - 1+ L n - 2Nos números de Fibonacci não existe uma unidade útil, portanto, não usamos a pilha de Fibonacci.Classificação Suave :: Smoothsort
O algoritmo final:- I. Crie um monte de pilhas de Leonard a partir da matriz, cada uma das quais é uma árvore de classificação.
- I.1 Itere os elementos da matriz da esquerda para a direita.
- II.1 Verificamos se, usando o elemento atual, é possível combinar os dois heaps mais à esquerda no heap existente dos heaps de Leonard:
- II.1.a. Se sim, então combinamos os dois montes mais à esquerda em um, o elemento atual se torna a raiz desse heap, separamos o heap combinado.
- II.1.b. Caso contrário, adicione o elemento atual como um novo heap (que consiste em um nó até agora) ao heap existente de Leonard heaps.
- II. , :
- II.1. . , .
- II.2. ( ) ( ).
- II.3. , . .
- II.4. ( ), .
- II.5 Depois de mover o elemento máximo para o final, a parte classificada da matriz aumentou e a parte não classificada diminuiu. Repita as etapas II.1-II.4 para a parte restante não classificada da matriz.
Exemplo de implementação do 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)
Complexidade do tempo
Se usarmos uma matriz quase ordenada como entrada, a visualização mostra por que essa matriz é processada muito mais rapidamente.A economia ocorre apenas devido à peneiração. Em dados quase ordenados, as peneiras afundam na árvore, inclusive após os montões serem gradualmente dissolvidos no segundo estágio. Nos dados inicialmente aleatórios, a peneiração é mais cara, uma vez que geralmente cai em sua pilha para o último nível.Vamos estimar a complexidade do tempo total.No primeiro estágio, iteramos sobre n elementos, adicionando-os às pilhas já existentes à esquerda. A adição ao heap em si é ignorada em O (1), mas, para o heap, você precisa fazer uma peneira. Nos dados ordenados, uma peneiração superficial geralmente custa O (1) para um elemento adicionado ao heap. Em dados não ordenados, a peneiração para cada adição é calculada em O (log n ), uma vez que, como resultado da aleatoriedade, a peneiração deve passar pelos níveis da árvore frequentemente até o fundo.Portanto, no primeiro estágio, a melhor complexidade de tempo é:para dados quase ordenados - O ( n ),para dados aleatórios - O ( n log n ).Para o segundo estágio, a situação é semelhante. Ao trocar o próximo máximo, você novamente precisa peneirar o heap na raiz do qual ele estava. E as métricas de peneiração para dados ordenados e desordenados serão diferentes.No segundo estágio, a melhor complexidade de tempo é a mesma do primeiro:para dados quase ordenados - O ( n ),para dados aleatórios - O ( n log n ).Adicionando complexidade de tempo para o primeiro e o segundo estágio:para dados quase ordenados - O (2 n ) = O ( n ),para dados aleatórios - O (2 n log n ) = O ( n log n ).Em geral, a pior e média complexidade de tempo para uma classificação suave é O ( n log n ).Dijkstra em seus cálculos (com os quais não vou aborrecê-lo) provou que a melhor complexidade tende suavemente a O ( n ) do que quanto mais ordenados os dados recebidos. Daí o nome - classificação suave.Complexidade extra de memória
Para decompor os dados em um monte de pilhas de Leonard, basta lembrar exatamente quais números de Leonardo estão envolvidos em cada etapa. Conhecendo esses números, os montões são alinhados algoritmicamente. Essa série de números cresce muito rapidamente, portanto, mesmo para matrizes grandes, você precisará de um conjunto muito pequeno de números de Leonard.Classificação de heap binomial :: Classificação de heap binomial
Existe uma estrutura de árvore, muito semelhante à que resolvemos - uma pilha binomial . Esse também é um monte de montes de tamanhos diferentes, em cada um dos quais o número de nós é uma potência de dois. Qualquer matriz de qualquer número de elementos pode ser expandida para este heap, pois qualquer número natural é decomposto na soma de dois graus diferentes.Em princípio, você pode fazer uma classificação suave com base em binômios:Funcionará mais rápido? Dificilmente. A pilha binomial não é binária e, no último artigo, descobrimos que aumentar o número de descendentes não acelera, mas retarda a tela . Além disso, você pode observar que o heap binomial tem ramificações mais longas, e é por isso que as regiões ordenadas vizinhas da matriz serão um pouco mais lentas para se conectar.Não se sabe se o heap binomial de Dijkstra era geralmente considerado como uma base possível para seu algoritmo. Seja como for, a pilha de Leonardov é provavelmente mais ideal.Trailer da próxima série
No entanto, mesmo que uma pilha binomial não seja a melhor opção para uma classificação suave, você não deve descartá-la completamente.Se a árvore binomial for ligeiramente modificada e idéias completamente diferentes (muito ousadas) forem usadas para contorná-la, obteremos um algoritmo original e eficaz que possui suas próprias vantagens. Sobre o que vamos falar na próxima vez?Clique na animação para ir para o artigo com a próxima classificação por pilha.Referências
O número Leonardo suave / suave , pilha binomial / pilha binomial Artigos da série:
A classificação suave de hoje foi adicionada ao aplicativo AlgoLab. Bem como um bônus - e classificação com uma pilha binomial. Então, quem quer direcionar pessoalmente os dados nos heap - atualize o arquivo excel com macros.