Classificar em uma pilha (também é uma classificação piramidal) em Habré já foi lembrado com uma boa palavra mais de uma ou duas vezes, mas essa sempre foi uma informação bastante conhecida. Todo mundo conhece a pilha binária usual, mas a teoria dos algoritmos também possui: umapilha n; um monte de montes com base nos números de Leonardo; Deramide (um híbrido de heap e árvore de pesquisa binária); mini pilha de torneios; pilha espelho (reversa); pilha fraca; Pilha de Jung; pilha binomial; e Deus sabe que outros montões ...E os representantes mais inteligentes da ciência da computação em anos diferentes propuseram seus algoritmos de classificação usando essas estruturas piramidais. Quem se importa com o que eles fizeram - para aqueles que estamos iniciando uma pequena série de artigos dedicados à classificação usando essas estruturas. O mundo dos montões é diverso - espero que você esteja interessado.
Este artigo foi escrito com o apoio da EDISON.
Estamos envolvidos no desenvolvimento de aplicativos móveis e fornecemos serviços de teste de software .
Adoramos a teoria dos algoritmos! ;-)
Existe essa classe de algoritmos - ordenando por escolha. A idéia geral é que a parte não ordenada da matriz seja reduzida devido ao fato de procurar os elementos máximos que são reorganizados em uma área classificada crescente.Classificar a escolha usual é força bruta. Se, em busca de máximos, é simples passar linearmente pela matriz, a complexidade de tempo de um algoritmo desse tipo não pode exceder O ( n 2 ).Um monte
A maneira mais eficiente de trabalhar com os altos da matriz é organizar os dados em uma estrutura de árvore especial, conhecida como heap . Essa é uma árvore na qual todos os nós pai não são menos que nós descendentes.Outros nomes da pilha - a pirâmide , a árvore de classificação .Vejamos como pode ser fácil e quase gratuito apresentar uma matriz na forma de uma árvore.Pegue o primeiro elemento da matriz e considere que essa é a raiz da árvore - um nó do 1º nível. Os próximos 2 elementos são nós do 2º nível, os descendentes direito e esquerdo do elemento raiz. Os próximos 4 elementos são nós do terceiro nível, os descendentes direito / esquerdo do segundo / terceiro elemento da matriz. Os próximos 8 elementos são nós do 4º nível, descendentes de elementos do 3º nível. Etc. Nesta imagem, os nós da árvore binária estão claramente localizados estritamente abaixo dos elementos correspondentes na matriz:Embora as árvores nos diagramas sejam mais frequentemente representadas em uma varredura:Se você observar esse ângulo, ficará claro por que a classificação por um grupo é chamada de classificação piramidal. Embora isso seja quase o mesmo que se você chamar um elefante de xadrez de oficial, uma torre de tura e uma rainha de rainha.Os índices para os descendentes do i- ésimo elemento são determinados por elementar (se o índice do primeiro elemento da matriz for considerado igual a 0, como é habitual na maioria das linguagens de programação):Descendente esquerdo de 2 × i + 1,o filho certo: 2 × i + 2(eu estou nos gráficos e nas animações, tradicionalmente, os índices de matrizes começam com 1, onde as fórmulas são ligeiramente diferentes: filho esquerdo: 2 × ie filho direito: 2 × i + 1, mas essas já são pequenas nuances aritméticas).Se a prole resultante dessas fórmulas, os índices ultrapassarem a matriz, significa que o i- ésimo item não possui filhos. Também pode acontecer que o i- ésimo elemento seja um descendente à esquerda (cai no último elemento da matriz em que um número ímpar de elementos), mas não há um direito.Portanto, qualquer matriz pode ser facilmente representada na forma de uma árvore, no entanto, isso ainda não é um monte, porque, na matriz, alguns elementos descendentes podem ser maiores que os elementos pai.Para que nossa árvore, criada com base na matriz, se torne um monte, ela precisa ser peneirada corretamente.Peneirar
A alma de escolher um grupo é peneirada.A peneiração de um elemento é que, se for menor do que os descendentes combinados em uma cadeia inextricável, esse elemento deverá ser movido o mais baixo possível, e os descendentes maiores deverão ser aumentados 1 nível acima.A imagem mostra o caminho de peneiração do item. A cor azul indica o elemento para o qual a peneiração é realizada. Verde - descendentes maiores no galho. Eles serão aumentados um nível acima, porque são maiores em tamanho do que o nó azul para o qual a tela é feita. O próprio elemento do nó azul superior será movido para o local do descendente mais baixo da cadeia verde.É necessário um peneiramento para fazer uma árvore de classificação fora de uma árvore comum e para apoiar ainda mais a árvore nesse estado (de classificação).Nesta imagem, os elementos da matriz são redistribuídos para que já estejam dispostos em um heap. Embora a matriz seja decomposta em uma árvore de classificação, ela ainda não foi classificada (crescente ou decrescente), embora todos os descendentes na árvore sejam menores que seus nós principais. Mas o elemento mais máximo na árvore de classificação está sempre na raiz principal, o que é muito importante.Heap Sort :: Heapsort
O algoritmo é realmente simples:- Etapa 1. Formamos uma árvore de classificação de toda a matriz. Para fazer isso, passamos da direita para a esquerda os elementos (do último para o primeiro) e, se o elemento tem descendentes, fazemos uma seleção.
- 2. . , . ( ) . , .. . , — . , .
Código Python para uma implementação clássica de classificação 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
Complexidade do algoritmo
Por que um heap simples é bom - ele não precisa ser armazenado separadamente, ao contrário de outros tipos de árvores (por exemplo, uma árvore de pesquisa binária baseada em uma matriz deve ser criada antes do uso). Qualquer matriz já é uma árvore na qual, em movimento, você pode identificar imediatamente os pais e descendentes. A complexidade da memória adicional é O ( 1 ), tudo acontece imediatamente.Quanto à complexidade do tempo, depende da peneiração. Uma única peneiração é ignorada em O (log n ) . Primeiro, analisamos n elementos para construir o heap inicial a partir da matriz - esta etapa leva O ( n log n ) . Na segunda etapa, quando tiramos nos máximos atuais da pilha, fazemos uma única peneiração para a parte restante não classificada, ou seja, esse estágio também nos custa O ( n log n ) .Complexidade do tempo total: O ( n log n ) + O ( n log n ) = O ( n log n ).Além disso, a classificação piramidal não apresenta casos degenerados nem melhores. Qualquer matriz será processada a uma velocidade decente, mas não haverá degradação ou registros.A classificação de heap, em média, é um pouco mais lenta que a classificação rápida. Mas para o quicksort, você pode escolher uma matriz matadora na qual o computador trava, mas para o heapsort - não.:: Ternary heapsort
Vamos olhar para a pilha ternária. Você não acreditará no binário, ele difere apenas no fato de os nós pais terem um máximo de não dois, mas três descendentes. Na pilha ternária para o i- ésimo elemento codifica três filhos calculados de maneira semelhante (se o primeiro índice do elemento = 0):O descendente esquerdo 3 × i + 1Descendente médio 3 × i + 2descendente direito 3 × i + 3(Se os índices começam com 1, como nas animações deste artigo, e nessas fórmulas você só precisa subtrair uma).Processo de classificação:Por um lado, o número de níveis na árvore diminui acentuadamente em comparação com a pilha binária, o que significa que, em média, haverá menos trocas durante a peneiração. Por outro lado, para encontrar o descendente mínimo, serão necessárias mais comparações - porque os descendentes agora não são dois, mas três cada. Em geral, em termos de complexidade de tempo - em algum lugar que encontramos, em algum lugar que perdemos, mas em geral a mesma coisa. Os dados no heap ternário são classificados um pouco mais rápido que no binário, mas essa aceleração é muito pequena. Em todas as variações da classificação piramidal, os desenvolvedores dos algoritmos preferem usar a opção binária, porque o ternário é supostamente mais difícil de implementar (embora seja "mais difícil" adicionar algumas ou três linhas extras ao algoritmo), e o ganho de velocidade é mínimo.Classificar por pilha n-heap :: N-narny heapsort
Obviamente, você não pode parar por aí e adaptar a classificação por vários grupos para qualquer número de descendentes. Talvez se você continuar aumentando o número de descendentes, poderá aumentar significativamente a velocidade do processo?Para o i- ésimo elemento dos índices da matriz (se a contagem de zero), seus N descendentes computaram de maneira muito simples:1º descendente: N × i + 12º descendente: N × i + 23º descendente: N × i + 3...Nésimo descendente: código N × i + NPython para classificação por um N-heap:
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
No entanto, mais não significa melhor. Se você levar a situação ao limite e levar N descendentes para uma matriz de N elementos, a classificação por vários degrada para de acordo com a escolha usual. Além disso, também será uma versão piorada da classificação por seleção, porque serão executados gestos sem sentido: a peneiração primeiro colocará o máximo em primeiro lugar na matriz e, em seguida, enviará o máximo até o fim (na classificação de seleção, o máximo será enviado imediatamente ao final).Se a pilha ternária ultrapassar minimamente o binário, o quádruplo já estará perdendo. Encontrar o máximo de descendentes entre vários torna-se muito caro.Trailer da próxima série
Portanto, a principal desvantagem do binário / ternário / n-heap é que a incapacidade de saltar em sua complexidade é maior que O ( n log n ) . A saída do impasse é usar variedades de heap mais sofisticadas na classificação. Em uma semana, vamos nos familiarizar com o que Edsger Dijkstra pensa sobre isso.Clique na animação para ir ao artigo com a seguinte classificação por váriosReferências
Pilha / pirâmideArtigos da série:
O aplicativo AlgoLab adicionou a classificação por n-heap. Para selecionar o número de descendentes, no comentário na célula desse tipo, você precisa especificar um número para n. O intervalo de valores possíveis é de 2 a 5 (não faz mais sentido, porque para n> = 6, a animação com três níveis de aninhamento em uma escala normal não é garantida para caber na tela).