🛷 💪🏾 👏🏿 Classificação de pilha fraca 🐶 😩 🚣🏻

De todo o zoológico, essa estrutura é talvez a mais incomum. Ao mesmo tempo, a simplicidade elegante do algoritmo corresponde à sua incrível excentricidade.

Ao classificar usando um heap fraco, sempre há menos comparações e trocas do que usar um heap regular. Então, sim, uma pilha fraca é mais forte que uma pilha comum.

Este artigo foi escrito com o apoio da EDISON.

Estamos envolvidos na criação de software embarcado , bem como no desenvolvimento de aplicativos e sites da web .

Adoramos a teoria dos algoritmos! ;-)

Pilha fraca

Um heap regular é uma árvore de classificação na qual qualquer pai é maior (ou igual) que qualquer um de seus descendentes. Em uma pilha fraca, esse requisito é enfraquecido - qualquer pai é maior que (ou igual a) qualquer descendente apenas de sua subárvore direita. Na subárvore esquerda, os descendentes podem ser menores e maiores que o pai, então você tem muita sorte.

Essa abordagem pode reduzir significativamente o custo de manutenção do conjunto de dados em um estado de heap. Afinal, é necessário garantir que o princípio “um descendente não seja mais que um pai” não para toda a estrutura, mas apenas para metade dela. Ao mesmo tempo, uma pilha fraca, não sendo uma árvore de classificação 100%, não é pior do que uma pilha comum e, de certa forma, ainda melhor. Fez metade da batalha - ande com ousadia!

Como a raiz da pilha, mesmo que fraca, precisa exatamente do elemento maior, a raiz da subárvore esquerda não.

Minimizar o número de comparações

Ronald D. Dutton, especialista em algoritmos e teoria de grafos, nos apresentou um grupo fraco em 1993. Uma pilha conceitualmente fraca é mais difícil de entender (mas é mais provável que essa dificuldade não seja na complexidade, mas na extravagância, você precisa quebrar seus padrões de consciência pelo joelho) do que uma pilha comum, por isso não recebeu muita distribuição prática. No entanto, quando Dutton inventou essa estrutura, ele não apenas queria praticar abstrações abstratas, mas também buscava um objetivo completamente pragmático.

Existe um limite teórico mais baixo para estimar o número mínimo de comparações (naquelas ordenações em que essas comparações são amplamente usadas):

log n ! = n log n - n / ln 2 + O (log n), onde 1 / ln 2 = 1,4426

Na classificação por um heap fraco, o número de comparações é minimizado e está próximo o suficiente do limite inferior.

Isso pode ser de importância prática se você precisar organizar objetos cuja comparação seja cara, por exemplo, se for para classificar cadeias longas.

Malabaristas descendentes

"Esquerda" e "direita" em uma pilha fraca são um fenômeno situacional. Uma subárvore pode ser descendente esquerda ou direita para seu nó pai - além disso, essa relação "esquerda / direita" para a subárvore e o pai pode alternar repetidamente de um valor para o oposto durante o processo.

Indicar para o pai que tem o filho certo e a filha esquerda não é simples, mas muito simples. Para fazer isso, você precisa de um bitmap adicional (que consiste apenas em valores de 0/1) para os nós que têm descendentes.

Lembre-se de como o índice é o i- ésimo elemento pai, definimos os índices de seus descendentes esquerdo e direito em uma pilha convencional (índices da matriz medidos a partir de zero):

Descendente esquerdo 2 × i + 1
Descendente direito 2 × i + 2

Em uma pilha fraca, temos uma cereja no bolo - uma raiz que possui apenas a subárvore direita, portanto, ajustaremos essas fórmulas para os índices descendentes adicionando um deslocamento reverso para 1 posição:

Descendente esquerdo: 2 × i
Descendente direito: 2 × i + 1

E finalmente , precisava de bitmap adicional (chame de bit ), em que o i- ésimo elemento observado era se a troca de lugar entre as subárvores esquerda e direita. Se o valor para um elemento for 0, não houve troca. Se o valor for 1, os filhos esquerdo e direito vão na ordem oposta. E as fórmulas nesse caso são as seguintes:

Descendente esquerdo: 2 × i + BIT [ i ]
Descendente direito: 2 × i + 1 - BIT [ i ]

É assim que parece. Os elementos cujos descendentes estão localizados "vice-versa" são destacados em azul. Os valores na matriz BIT para eles são 1.

Você pode verificar substituindo os valores-pai ie o 0/1 correspondente da matriz BIT nas fórmulas descendentes - os índices dos descendentes serão exibidos conforme necessário.

Como você pode ver, para qualquer pai trocar as subárvores esquerda e direita, na própria matriz, o grupo de elementos não precisa ser movido para lugar algum. Somente o valor 0/1 do pai na matriz BIT é alterado e é isso.

Próximo - uma sessão de mágica com sua subsequente exposição.

Construa uma pilha fraca

Trocar descendentes esquerdo e direito é a principal ferramenta para converter em um monte fraco um conjunto de dados de uma matriz.

No processo de formação do heap fraco primário, precisamos classificar os elementos da matriz na ordem inversa (começando pela última) e para cada um deles encontrar a ramificação do primeiro pai (direito), para o qual será a subárvore correta.

Se o elemento é o descendente certo de alguém , você não precisa ir muito longe. Seu pai imediato é o que você precisa:

Se o elemento for descendente esquerdo de alguém , você precisará subir vários níveis antes de conhecer o avô desejado, para o qual o elemento está na subárvore direita:

Então você precisa comparar o descendente e o progenitor encontrado em algum lugar acima. E se o descendente for maior que o progenitor, o seguinte deverá ser feito:

Se o descendente tiver seus descendentes, troque as subárvores esquerda e direita (ou seja, alterne 0/1 na matriz BIT para esse elemento).
Troque os valores do nó descendente e do nó progenitor.

Dê uma olhada em um exemplo específico. Digamos que a seguinte situação surgiu:

Para o elemento da matriz A [6] = 87, foi encontrado o progenitor necessário A [1] = 76.
O progenitor A [1] é menor que o elemento A [6] (76 <87).
O elemento A [6] possui subárvores esquerda e direita (marcadas em tons de verde).
Você precisa trocar essas subárvores
(ou seja, para o elemento A [6] na matriz BIT , altere o valor de 0 para 1).
Também é necessário trocar os valores dos elementos A [6] e A [1].

Após as ações necessárias serem concluídas:

Para o elemento A [6], as subárvores esquerda e direita foram trocadas
(ou seja, na matriz BIT do elemento A [6], o valor de 0 foi alterado para 1).
Houve também uma troca de valores entre A [6] e A [1].

Se você percorrer a matriz do fim ao início e, ao longo do caminho, executar este procedimento para todos os elementos, terá uma pilha fraca.

Por que esse mecanismo estranho funciona é uma explicação mais próxima do final do artigo.

Analisando uma pilha fraca

Um heap é um heap se o elemento máximo estiver na raiz. Usando esse fato, todas as classificações de heap funcionam da mesma maneira. A raiz (onde o máximo está localizado) troca valores com o último elemento da parte não classificada da matriz - como resultado, a parte não classificada da matriz diminui e a parte classificada da matriz aumenta. Após essa troca, o heap deixa de ser um heap, pois o elemento máximo atual não está mais em sua raiz. O heap precisa ser restaurado, ou seja, tornar a árvore resultante um heap novamente - encontre outro elemento máximo e mova-o para a raiz.

Como recuperar uma pilha binária regular, sabemos - com a ajuda de uma peneira . Mas como restaurar uma pilha fraca? Para fazer isso, faça o seguinte.

Da raiz descemos os descendentes esquerdos (da direita para a mais baixa):

Em seguida, subimos os descendentes esquerdos de volta e, ao longo do caminho, cada descendente esquerdo é comparado com um elemento na raiz da pilha. E se o próximo descendente esquerdo for maior que a raiz, faremos o mesmo que no estágio anterior: no descendente esquerdo, trocamos as subárvores (se ele tiver um) e alteramos os valores do descendente e raiz esquerdos.

Como resultado, restauraremos o heap fraco - o elemento máximo que está na árvore restante aparecerá na raiz.

E, novamente, temos este carrossel místico com subárvores que se substituem. Então, qual é o segredo do sucesso? Por que, se durante a troca de nós com valores, os descendentes esquerdo e direito do nó inferior são trocados, terminamos com uma matriz classificada? Você nunca vai adivinhar, embora a resposta seja simples em seu gênio.

Classificação fraca de heap :: Classificação fraca de heap

Então, o algoritmo final:

I. :
- I.1. -.
- I.2. «» .
- I.3. .
- I.4. , :
  - I.4.. ( ⇔ ) , .
  - I.4.. «» .
II. , :
- II.1. .
- II.2. . .
- II.3. , . :
  - II.3.. .
  - II.3.. , .
  - II.3.. , , :
    - II.3.c. 1. Trocamos subárvores (esquerda ⇔ direita) com descendentes pelo nó no qual o descendente esquerdo atual está localizado.
    - II.3.c.2. Alteramos a raiz da pilha e o nó com o filho esquerdo atual.
- II.4 Na raiz do heap fraco está novamente o elemento máximo para a parte restante não classificada da matriz. Retornamos ao parágrafo II.1 e repetimos o processo até que todos os elementos sejam classificados.

Animação (os índices de matriz em minhas animações começam com um):

Código C ++

Na parte inferior da seção "Links", os interessados podem se familiarizar com a implementação dessa classificação em C ++. Aqui, dou apenas a parte que ilustra o próprio algoritmo.

#define GETFLAG(r, x) ((r[(x) >> 3] >> ((x) & 7)) & 1)
#define TOGGLEFLAG(r, x) (r[(x) >> 3] ^= 1 << ((x) & 7))

void WeakHeap::WeakHeapMerge(unsigned char *r, int i, int j) {
  if (wheap[i] < wheap[j]) {//""  ?
    //  ,   
    //( "",   "")
    TOGGLEFLAG(r, j);
    //  ""  
    swap(wheap[i], wheap[j]);
  }
}

void WeakHeap::WeakHeapSort() {
  int n = Size();
  if(n > 1) {
		
    int i, j, x, y, Gparent;
    int s = (n + 7) / 8;
    unsigned char * r = new unsigned char [s];
		
    //  ,    
    // "",   ""
    for(i = 0; i < n / 8; ++i) r[i] = 0;
		
    //   
    for(i = n - 1; i > 0; --i) {
      j = i;
      //    , 
      //   ""  
      while ((j & 1) == GETFLAG(r, j >> 1)) j >>= 1;
      //       ""  
      Gparent = j >> 1;
      //  ,   
      //   ""
      WeakHeapMerge(r, Gparent, i);
    }
		
    //      -->
    //  -->    
    for(i = n - 1; i >= 2; --i) {
      //      
      //       
      swap(wheap[0], wheap[i]);
      x = 1;
      //    "" 
      while((y = 2 * x + GETFLAG(r, x)) < i) x = y;
      //  ""     
      //        
      while(x > 0) {
        WeakHeapMerge(r, 0, x);
        x >>= 1;
      }
    }
    //  -   
    //    
    swap(wheap[0], wheap[1]);
    delete[] r;
  }
}

Eu gosto especialmente de como a árvore binária é percorrida fácil e naturalmente usando operações bit a bit.

Complexidade extra de memória

Parece O ( n ) - é necessária uma matriz adicional, na qual a ordem das subárvores esquerda / direita é fixada para nós com descendentes (cerca da metade da matriz).

No entanto, existe uma opinião de que a complexidade da classificação aqui é realmente O (1)! Para um elemento, precisamos apenas de um bit adicional (zero / um) para indicar a ordem dos descendentes. Se ordenarmos, por exemplo, cadeias de caracteres, é bastante possível anexar esse bit adicional ao próprio elemento.

Outra maneira de transformar O ( n ) em O (1) é armazenar sinalizadores em um número inteiro. Expansão binária de números - um conjunto de zeros e os responsáveis pela ordem das subárvores de todos os elementos da matriz. O i- ésimo elemento da matriz corresponde ao i- ésimo do número.

Complexidade do tempo

Com o tempo, O ( n log n ) é o mesmo que um heap regular. Ao classificar linhas (especialmente as longas), um heap fraco pode ser mais rápido que um heap normal. Mas isso é se classificarmos as longas filas. Se ordenarmos os números, então, de acordo com os rumores, um monte comum é mais rápido de gerenciar.

Peneiração total

No estágio de formação do heap inicial fraco, por analogia com o heap usual, a idéia bastante óbvia sugere elevar elementos grandes o mais alto possível. Ou seja, se trocássemos os valores do nó inferior e de seu ancestral, seria lógico repetir imediatamente as etapas do ancestral - encontrar o ancestral direito mais próximo para ele e comparar (e se também for necessário trocar valores + troca de subárvores). E, se possível, eleve um elemento grande até a raiz. É assim que parece no primeiro estágio (as ações no segundo estágio do algoritmo permanecem inalteradas):

A pontuação de complexidade do tempo permanece a mesma.

Pilha binomial

Tudo o que foi feito até agora é uma decepção, uma ilusão. Obviamente, formalmente realizamos algumas manipulações com a árvore binária, alteramos os nós com valores, reorganizamos as subárvores e tudo mais. No entanto, o algoritmo tem um fundo duplo, sobre o qual iremos agora analisar.

Para entender esse tipo, você precisa entender o que realmente é uma pilha fraca.

Se tomarmos uma matriz na qual o número de elementos é uma potência de dois, a pilha fraca e a pilha binomial construída com base em sua base são isomórficas.

Não olhe para o fato de que um heap fraco é binário e o binômio não. Em uma pilha fraca, as subárvores esquerda e direita são essencialmente diferentes. A subárvore direita é um descendente no sentido clássico, mas a subárvore esquerda é um "irmão". Embora não seja. A subárvore esquerda não é nem um "irmão", mas um vetor de "irmãos" com menos nós.

No entanto, a pilha fraca e a pilha binomial não são 100% iguais, embora sejam os parentes mais próximos. A diferença é óbvia, se você pegar uma matriz cujo número de elementos não seja igual a 2 ⁿ . A decomposição binomial de tal matriz fornecerá uma lista conectada de vários heaps ideais (o número de nós em cada um deles é uma certa potência de dois):

Uma pilha fraca nesse caso será uma árvore binária imperfeita:

A pilha binomial e a pilha fraca são irmãos gêmeos. O DNA é o mesmo, embora na aparência você não possa dizer.

Algoritmo secreto

Dado que uma pilha fraca é uma pilha criptobinomial, as subárvores aleatórias encontram subitamente uma explicação simples.

Com uma pilha fraca, varra o ouropel pseudobinário e observe as relações reais entre os nós no estilo de pilha binomial. Tudo fica claro.

De fato:

Não há "fraqueza", é uma árvore de classificação (não binária) em que o princípio "qualquer pai é maior que qualquer de seus descendentes" é alcançado e mantido.
Em todos os estágios, comparamos os descendentes não com seus ancestrais, mas com seus pais imediatos.
O que parece ser uma troca de valores entre um descendente e um ancestral + uma troca de lugares de subárvores em um descendente - acaba sendo a troca da própria proporção (descendente / pai / mãe). Se o nó pai for menor que o descendente por valor, o próprio pai se tornará o descendente e o descendente se tornará o pai.

Aqui está uma visualização honesta:

Na próxima série

A próxima pilha que eu gostaria de falar é a minha favorita - a árvore cartesiana. Isso não é apenas um monte, mas também uma árvore de pesquisa binária . Mas então, primeiro, no próximo artigo, algo interessante precisa ser esclarecido sobre as árvores BST. E só então, através do artigo, e sobre conversas cartesianas.

Referências

Heap fraco , heap binomial / heap binomial

C ++ Implementação de heap fraco

Ronald D. Dutton: Página pessoal , perfil do site da UCF

Heaps e amigos fracos: desenvolvimentos recentes

A estrutura de dados do Weak-Heap: variantes e aplicativos

sobre o desempenho do WEAK-HEAPSORT

Adaptive heapsort: Código fonte

Sergey Kopeliovich - Sala de aula - Pilha fraca (de 48:32 a 1:16:06)

Artigos da série:

Aplicativo Excel AlgoLab.xlsm
Classificações de Câmbio
Classificações de inserção
Classificar por seleção
- Tipos de pilhas: N-pirâmides
- Classificações da pilha: números de Leonardo
- Classificação de heap: heap fraco
- Tipos de Cacho: Árvore Cartesiana
- Outras classificações de pilha: pilha de espelhos, mini-pilha, peneiração de baixo para cima
- Tipos de Heap: Jung Heap
Mesclar classificações
Classificar por distribuição
Classificação híbrida

A classificação de hoje é adicionada ao aplicativo AlgoLab por um grupo fraco, que o usa - atualize o arquivo do Excel com macros.

Nos comentários da célula com o nome da classificação, você pode especificar algumas configurações. Se você definir siftup = 1, a classificação utilizará a triagem completa no primeiro estágio (por padrão siftup = 0).

Se você prescrever binomial = 1, a árvore será um “heap binomial” (por padrão, binomial = 0, ou seja, apenas um heap fraco).

Classificação de pilha fraca