Pilha binomial - Binomial heap

Na ciência da computação , um heap binomial é uma estrutura de dados que atua como uma fila de prioridade, mas também permite que pares de heaps sejam mesclados. É importante como uma implementação do tipo de dados abstratos de heap mesclável (também chamado de heap meldable ), que é uma fila de prioridade que dá suporte à operação de mesclagem. Ele é implementado como um heap semelhante a um heap binário, mas usando uma estrutura de árvore especial que é diferente das árvores binárias completas usadas por heaps binários. Os montes binomiais foram inventados em 1978 por Jean Vuillemin .

Heap binomial

Um heap binomial é implementado como um conjunto de árvores binomiais (compare com um heap binário , que tem a forma de uma única árvore binária ), que são definidas recursivamente da seguinte maneira:

Uma árvore binomial de ordem 0 é um único nó
Uma árvore binomial de ordem tem um nó raiz cujos filhos são raízes de árvores binomial de ordens , , ..., 2, 1, 0 (nesta ordem). ${\ displaystyle k}$ ${\ displaystyle k-1}$ ${\ displaystyle k-2}$

Árvores binomiais de ordem 0 a 3: cada árvore possui um nó raiz com subárvores de todas as árvores binomiais de ordem inferior, que foram destacadas. Por exemplo, a árvore binomial de ordem 3 está conectada a uma árvore binomial de ordem 2, 1 e 0 (destacada como azul, verde e vermelho, respectivamente).

Uma árvore binomial de ordem possui nós e altura . O nome vem da forma: uma árvore binomial de ordem possui nós em profundidade , um coeficiente binomial . Por causa de sua estrutura, uma árvore de ordem binomial pode ser construída a partir de duas árvores de ordem anexando uma delas como o filho mais à esquerda da raiz da outra árvore. Esse recurso é fundamental para a operação de mesclagem de um heap binomial, que é sua principal vantagem sobre outros heaps convencionais. ${\ displaystyle k}$ ${\ displaystyle 2 ^ {k}}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle {\ tbinom {k} {d}}}$ ${\ displaystyle d}$ ${\ displaystyle k}$ ${\ displaystyle k-1}$

Estrutura de uma pilha binomial

Um heap binomial é implementado como um conjunto de árvores binomiais que satisfazem as propriedades do heap binomial :

Cada árvore binomial em um heap obedece à propriedade de heap mínimo : a chave de um nó é maior ou igual à chave de seu pai.
Pode haver no máximo uma árvore binomial para cada pedido, incluindo o pedido zero.

A primeira propriedade garante que a raiz de cada árvore binomial contenha a menor chave da árvore. Conclui-se que a menor chave em todo o heap é uma das raízes.

A segunda propriedade implica que um heap binomial com nós consiste em no máximo árvores binomiais, onde é o logaritmo binário . O número e as ordens dessas árvores são determinados exclusivamente pelo número de nós : há uma árvore binomial para cada bit diferente de zero na representação binária do número . Por exemplo, o número decimal 13 é 1101 em binário, e, portanto, um heap binomial com 13 nós consistirá em três árvores binomiais de ordens 3, 2 e 0 (veja a figura abaixo). ${\ displaystyle n}$ ${\ displaystyle 1+ \ log _ {2} n}$ ${\ displaystyle \ log _ {2}}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle 2 ^ {3} + 2 ^ {2} + 2 ^ {0}}$

Exemplo de um heap binomial contendo 13 nós com chaves distintas.
O heap consiste em três árvores binomiais com ordens 0, 2 e 3.

O número de maneiras diferentes pelas quais os itens com chaves distintas podem ser organizados em um heap binomial é igual ao maior divisor ímpar de . Pois esses números são ${\ displaystyle n}$ ${\ displaystyle n!}$ ${\ displaystyle n = 1,2,3, \ dots}$

1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... (sequência A049606 no OEIS )

Se os itens são inseridos em uma pilha binomial em uma ordem uniformemente aleatória, cada um desses arranjos é igualmente provável. ${\ displaystyle n}$

Implementação

Como nenhuma operação requer acesso aleatório aos nós raiz das árvores binomiais, as raízes das árvores binomiais podem ser armazenadas em uma lista encadeada , ordenada por ordem crescente da árvore. Como o número de filhos de cada nó é variável, não funciona bem para cada nó ter links separados para cada um de seus filhos, como seria comum em uma árvore binária ; em vez disso, é possível implementar essa árvore usando links de cada nó para seu filho de ordem superior na árvore e para seu irmão de ordem menor seguinte. Esses ponteiros irmãos podem ser interpretados como os próximos ponteiros em uma lista vinculada dos filhos de cada nó, mas com a ordem oposta da lista vinculada de raízes: da ordem maior para a menor, em vez de vice-versa. Esta representação permite que duas árvores da mesma ordem sejam ligadas entre si, formando uma árvore da próxima ordem maior, em tempo constante.

Unir

Para fundir duas árvores binomiais da mesma ordem, primeiro compare a chave raiz. Como 7> 3, a árvore preta à esquerda (com nó raiz 7) é anexada à árvore cinza à direita (com nó raiz 3) como uma subárvore. O resultado é uma árvore de ordem 3.

A operação de mesclar dois heaps é usada como uma sub-rotina na maioria das outras operações. Uma sub-rotina básica dentro deste procedimento mescla pares de árvores binomiais da mesma ordem. Isso pode ser feito comparando as chaves nas raízes das duas árvores (as chaves menores em ambas as árvores). O nó raiz com a chave maior é transformado em filho do nó raiz com a chave menor, aumentando sua ordem em um:

function mergeTree(p, q)
    if p.root.key <= q.root.key
        return p.addSubTree(q)
    else
        return q.addSubTree(p)

Isso mostra a fusão de duas pilhas binomiais. Isso é realizado pela fusão de duas árvores binomiais da mesma ordem, uma a uma. Se a árvore mesclada resultante tiver a mesma ordem de uma árvore binomial em uma das duas pilhas, essas duas serão mescladas novamente.

Para fundir dois heaps de maneira mais geral, as listas de raízes de ambos os heaps são percorridas simultaneamente de maneira semelhante à do algoritmo de fusão , em uma sequência de ordens menores de árvores para ordens maiores. Quando apenas um dos dois heaps sendo mesclados contém uma árvore de ordem , esta árvore é movida para o heap de saída. Quando os dois heaps contêm uma árvore de ordem , as duas árvores são fundidas em uma árvore de ordem para que a propriedade de heap mínimo seja satisfeita. Posteriormente, pode ser necessário fundir esta árvore com alguma outra árvore de ordem em um dos dois heaps de entrada. No decorrer do algoritmo, ele examinará no máximo três árvores de qualquer ordem, duas das duas pilhas que fundimos e uma composta por duas árvores menores. ${\ displaystyle j}$ ${\ displaystyle j}$ ${\ displaystyle j + 1}$ ${\ displaystyle j + 1}$

function merge(p, q)
    while not (p.end() and q.end())
        tree = mergeTree(p.currentTree(), q.currentTree())
        
        if not heap.currentTree().empty()
            tree = mergeTree(tree, heap.currentTree())
        
        heap.addTree(tree)
        heap.next(); p.next(); q.next()

Como cada árvore binomial em uma pilha binomial corresponde a um bit na representação binária de seu tamanho, há uma analogia entre a fusão de duas pilhas e a adição binária dos tamanhos das duas pilhas, da direita para a esquerda. Sempre que ocorre um transporte durante a adição, isso corresponde a uma fusão de duas árvores binomiais durante a fusão.

Cada árvore tem ordem no máximo e, portanto, o tempo de execução é . ${\ displaystyle \ log _ {2} n}$ ${\ displaystyle O (\ log n)}$

Inserir

A inserção de um novo elemento em um heap pode ser feita simplesmente criando um novo heap contendo apenas esse elemento e, em seguida, mesclando-o com o heap original. Por causa da mesclagem, uma única inserção leva tempo . No entanto, isso pode ser acelerado usando um procedimento de mesclagem que atalhos a mesclagem depois que ela atinge um ponto onde apenas um dos heaps mesclados tem árvores de ordem maior. Com essa aceleração, em uma série de inserções consecutivas, o tempo total das inserções é . Outra maneira de afirmar isso é que (após a sobrecarga logarítmica para a primeira inserção em uma sequência) cada inserção sucessiva tem um tempo amortizado de (isto é, constante) por inserção. ${\ displaystyle O (\ log n)}$ ${\ displaystyle k}$ ${\ displaystyle O (k + \ log n)}$ ${\ displaystyle O (1)}$

Uma variante do heap binomial, o heap binomial skew , atinge o tempo de inserção de pior caso constante usando florestas cujos tamanhos de árvore são baseados no sistema numérico binário skew em vez do sistema numérico binário.

Encontre o mínimo

Para encontrar o elemento mínimo da pilha, encontre o mínimo entre as raízes das árvores binomiais. Isso pode ser feito com o tempo, pois há apenas raízes de árvores para examinar. ${\ displaystyle O (\ log n)}$ ${\ displaystyle O (\ log n)}$

Usando um ponteiro para a árvore binomial que contém o elemento mínimo, o tempo para esta operação pode ser reduzido para . O ponteiro deve ser atualizado ao realizar qualquer operação diferente de encontrar o mínimo. Isso pode ser feito em tempo por atualização, sem aumentar o tempo geral de execução assintótica de qualquer operação. ${\ displaystyle O (1)}$ ${\ displaystyle O (\ log n)}$

Excluir mínimo

Para excluir o elemento mínimo do heap, primeiro encontre esse elemento, remova-o da raiz de sua árvore binomial e obtenha uma lista de suas subárvores filhas (que são, cada uma delas, árvores binomiais, de ordens distintas). Transforme essa lista de subárvores em um heap binomial separado, reordenando-as da ordem menor para a maior. Em seguida, mescle esse heap com o heap original. Como cada raiz tem no máximo filhos, a criação desse novo heap leva tempo . A fusão de heaps leva tempo , portanto, toda a operação mínima de exclusão leva tempo . ${\ displaystyle \ log _ {2} n}$ ${\ displaystyle O (\ log n)}$ ${\ displaystyle O (\ log n)}$ ${\ displaystyle O (\ log n)}$

function deleteMin(heap)
    min = heap.trees().first()
    for each current in heap.trees()
        if current.root < min.root then min = current
    for each tree in min.subTrees()
        tmp.addTree(tree)
    heap.removeTree(min)
    merge(heap, tmp)

Tecla de diminuição

Depois de diminuir a chave de um elemento, ele pode se tornar menor que a chave de seu pai, violando a propriedade de heap mínimo. Se for esse o caso, troque o elemento por seu pai e, possivelmente, também por seu avô e assim por diante, até que a propriedade de heap mínimo não seja mais violada. Cada árvore binomial tem altura no máximo , então isso leva tempo. No entanto, esta operação requer que a representação da árvore inclua ponteiros de cada nó para seu pai na árvore, complicando um pouco a implementação de outras operações. ${\ displaystyle \ log _ {2} n}$ ${\ displaystyle O (\ log n)}$

Excluir

Para excluir um elemento do heap, diminua sua chave para infinito negativo (ou equivalentemente, para algum valor inferior a qualquer elemento no heap) e, em seguida, exclua o mínimo no heap.

Formulários

Veja também

Heap fraco , uma combinação das estruturas de dados de heap binário e de heap binomial

Referências

links externos

Duas implementações C de heap binomial (uma genérica e uma otimizada para chaves inteiras)
Implementação de Haskell de heap binomial
Implementação Common Lisp de heap binomial

Languages

In other projects