Heaps Binomiais

| Parte 1 | Parte 2 | Parte 3 | Parte 4 |

Esse post é sobre um trabalho acadêmico que fiz e ficou muito bom, bastante completo comparado as referências de outros sites. Por isso deixarei esse material de apoio para aqueles que um dia iram pesquisar sobre esse assunto.

Introdução

Para definir heaps binomiais é importante definir antes o que é uma Árvore Binomial. Árvores binomiais são formadas pela seguinte recursão:
· B(0), um vértice
· B(k) , são duas arvores binomiais B(k-1), onde a raiz de uma é o filho mais a equerda da outra.

Uma arvore binomial possui:

• 2^k nós;
• Altura k;
• nível i, possui nós, sendo i =0,1...k;
• A raiz Bk sempre terá grau k maior que todos os outros nós.

Um heap binomial é um conjunto dessas árvores binomiais com mais 2 propriedades:

• Toda árvore binomial tem a estrutura de um heap. Nos heaps, a chave de um nó é maior ou igual a chave do seu pai, assim cada nó da arvoré binomal irá possuir essa mesma propriedade.
• Outra propriedade é que dentro de um heap só pode haver uma única raiz com um determinado grau. Assim para um heap de n nós, haverá [log2 n] + 1. Uma forma mais simples é imaginar a representação binária do número de nós, por exemplo 10 é respresentado por 1010, 2^3 +2^1, assim o heap de 10 elementos será representado por duas árvores binominais B(3) e B(1).

Representação

A estrutura de dados de um nó do heap é:

•  key, onde será armazenada a chave do nó
•  p, ponteiro para o pai do nó
•  child, ponteiro para o filho mais a esquerda
• sibling, ponteiro para o irmão imediatamente à direita
•  degree, grau do nó (número de sub-árvores)
• Haverá uma estrutura do Heap que possui um ponteiro (head) para o nó inicial

| Parte 1 | Parte 2 | Parte 3 | Parte 4 |