Heap Binomiais (parte 4)

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

Operações (continuação)

Extract_Min

Função que remove o nó com a menor chave do Heap.

ExtractMin(H){
//Nesse trecho o código busca a raiz com a menor chave e a //remove junto com as suas sub-arvores 
minimumRoot = Minimum(H)
//Caso a raiz com a chave mínima estiver no início remove-se //logo
if minimumRoot = H-head  
H-head = H-head-sibling
else{ 
//Caso contrario tem que achar a posição dela
rootSearch = H-head
while rootSearch-sibling != minimumRoot { 
rootSearch = rootSearch-sibling
}
//Depois de encontrada é removida
rootSearch-sibling = rootSearch-sibling-sibling
}
//Caso essa raiz possuir sub-árvores, devem ser devolvidas ao //Heap
if(minimumRoot-child != null){
//Inverte a ordem das sub-árvores formando um heap
H' := Make_Heap()
last = NULL
no = minimumRoot-child

//A primeira sub-arvore que deve ser a ultima
//Para ser a ultima o nó a direita deve ser null
//Varre as sub-arvores mudando os seus ponteiros, 
//os nós a direita de um determinado nó devem ser aqueles que       //estavam a sua esquerda, invertendo assim a ordem das sub-//arvores
while no != null{   
next = no-sibling
no-sibling = last
last = no
no = next
}
//O início do heap aponta para os último que estava a direita
H'-head = last
//Junta esse Heap com o original   
H = Binomial-Heap-Union(H,H') 
}
return minimumRoot
}

 

Decrease_key


Função que diminui a chave de um nó X para um valor K e o realoca na posição correta do Heap.

Decrease_Key(H,x,k)
if k > x-key
then error "o valor é maior que a chave atual do nó"
x-key = k
atual = x
pai = atual-p
// Enquanto houver raiz e nova chave do nó for menor que a chave //do nó pai
while atual != NULL and atual-key < pai-key 
do 
troca atual-key com pai-key
//Se possui outros campos troca-se também
//Sobe a na árvore
atual = pai
pai = atual-p

Delete

Remove um nó qualquer do Heap.

Delete(H,x)
//Dado um nó qualquer torna a chave dele o menor possível e //remove-lo com a função extrair o mínimo. 
//Para atribuir o menor valor a chave pode buscar a menor chave //do Heap e decrementar um
Decrease-Key(H,x,-infinity)
Return Extract-Min(H)

Referência Bibliográfica

• Binomial Heap Wikipedia http://en.wikipedia.org/wiki/Binomial_heap
• Eduardo Camponogara Universidade Federal de Santa Catarina http://www.das.ufsc.br/~camponog/Disciplinas/DAS-9003/slides_CLR/l11-binomial-heaps.pdf
• Gabriel Pedro de Castro Unicamp http://www.ic.unicamp.br/~zanoni/mo637/aulas/heapsBinomiais.pdf
• Department Computer Science and Engineering, New York University(Animação) http://www.cse.yorku.ca/~aaw/Sotirios/BinomialHeap.html
• Binomial Trees, Bruno R. Preiss http://www.brpreiss.com/books/opus4/html/page371.html
• Algoritmos Teoria e Prática, Thomas H. Cormen Pg 365 á 379

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