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 |

Heaps Binomiais (parte 3)

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

Operações (continuação)

HeapMerge

Função que retorna uma lista de arvores binomiais de ordem de grau crescente a partir da união de dois heaps.

HeapMerge(H1,H2)
// Ambos Heaps apontam para uma raiz de menor grau, "a" apontara para o menor dessas duas raízes, "b" apontara para a outra
a = H1-head
b = H2-head
head[H1] = Min-Degree(a, b)
if H1-head = NIL
return
if H1-head = b
then b = a
a = H1-head
//Enquanto houver árvores do lado "b" continue unindo
while b != NULL do 
//Se não houver mais árvores a direita de "a", a árvore da direita de "a" será "b"
if a-sibling = NULL 
then a-sibling = b
return
else if a-sibling-degree < b-degree
//Se grau da raiz a direita de "a" for menor que grau de b, avance para "a" para o seu irmão à direita
then a = a-sibling
//Se não, precisa inserir a raiz "b" antes da raiz "a"
else c = b-sibling
b-sibling = a-sibling
a-sibling = b
a = a-sibling
b = c
return H1

Union

Função que retorna um heap a partir da união de depois heaps.

Binomial-Heap-Union(H1,H2)
H = Make_Heap()
//Monta uma lista de árvores binomiais dos dois heaps ordenadas por grau
H-head = HeapMerge(H1,H2)
//libera a memória ocupada por H1 and H2 mas não as listas que //eles apontam
if H-head = NULL
then return H
// Aqui há uma estrutura de dados X, possui os mesmos atributos //de um nó
// porém com mais dois: Prev (nó raiz da esquerda) Next (nó raiz //direita)
// Essa estrutura servirá para navegar entre as raízes e fazer //as operações
x-prev = NULL
x = H-head
x-next = x-sibling
while x-next != NULL //Enquanto houver raiz à direita
//Verifica se os graus da raiz atual e a próxima são //diferentes ou se há três raízes iguais em seqüência. Nesse //caso avança a navegação.
do if (x-degree !- next-x-degree) or
(next-x-sibling != NULL
and next-x-sibling-degree = x-degree)
then prev-x = x
x = next-x
//Se a chave da raiz atual for menor que o próximo, //a raiz atual será a nova raiz da nova árvore binomial com a //próxima raiz sendo seu filho mais a esquerda
// Não pode esquecer que a raiz a direita do próximo será a da //raiz atual
else if x-key <= next-x-key
then x-sibling = x-next-sibling 
Link(x-next,x)
//Se a chave atual for maior, o próximo nó será a nova raiz //com o nó atual sendo seu filho mais a esquerda. Dessa forma, o //nó a direita do nó anterior será o próximo nó, não havendo nó //anterior então o início da lista é o próximo nó.
else if prev-x = NIL   
then H-head = next-x
else x-prev-sibling = next-x
Binomial-Link(x,x-next)
x = x-next
x-next = x-sibling // No final sempre avança a                                     //navegação do próximo nó
return H

Insert_Heap

Função que insere um nó qualquer em um heap.

Insert_Heap(H,x)
//A idéia é muito simples, simplesmente cria-se um heap com um // único nó e usa a função de união nele 
H' = Make-Binomial-Heap()
x-p = NULL
x-child = NULL
x-sibling = NULL
x-degree = 0
H'-head = x
H = Binomial-Heap-Union(H,H')

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

Heaps Binomiais (parte 2)

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

Operações

As principais operações dos heaps binomiais e seus respectivos tempos no pior caso são:

• Make_Heap (Montar o Heap) Θ(1);
• Insert_Heap (Inserir) Θ (log2 n);
• Minimum (Mínimo) Θ(log2 n);
• Extract_Min (Extrair o mínimo) Θ(log2 n);
• Union (União) Θ(log2 n);
• Decrease_Key (Decrementar chave) Θ(log2 n);
• Delete (Excluir) Θ(log2 n).

Make_Heap

Função que cria o Heap

Make_Heap(){
H ← new no()
H-head ← NULL // Marca o pai como nulo, já que é o nível mais alto
return H
}

Minimum

Função que busca a menor chave do Heap. Tarefa fácil, já que os menores valores estão nas raízes.

Minimum(H){ // H é o Heap
ponteiroMin ← NULL
proximo ← H-head // Inicio das raízes
min ← ∞
// Varre todas as raízes e determina a menor chave
while proximo != NULL { 
if proximo-key < min {
min ← x-key
ponteiroMin ← x
}
proximo ← x-sibling
}
return ponteiroMin
}

Link

Função que une duas árvores B(k-1)

Link(y, z){
y-p ← z // Pai de y será z
// A raiz imediatamente a direita será o filho mais a esquerda de z
y-sibling ← z -child 
z-child ← y //Agora o filho mais a esquerda de z é y
// Aumenta o grau de z graças ao seu novo filho
z-degree ← z-degree + 1 
}

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

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 |

Bokusatsu Tenshi Dokuro-chan

Ultimamente existe vários lançamentos de animes, mas tantos que o humano só consegue acompanhar todos se não fazer mais nada na  vida. O pior é quando você assiste e se decepciona, perdeu um tempo precioso da sua vida! Para evitar isso, estou aqui pra recomendar esse anime supremo! História complexa e profunda? Para! Esquece isso, em compensação você ganhará muitas risadas nessa divertida comédia sangrenta!

A série (12 episódios) [download]

A história é muito simples, o autor criou um cenário e neles os personagens vão se encontrar e interagir, muito parecido com os seriados de comédia americano onde não início, meio ou fim. Os episódios são bastantes independentes, mas claro que alguns acontecimentos e personagens são inseridos no decorrer da história e permanecem, diferente de Simpsons onde o mundo pode acabar em um episódio que no outro eles agem como se nada daquilo aconteceu.
O garotinho protagonista se chama Kusakabe Sakura, que aprontou algo no futuro e o Todo-Poderoso envia um anjo chamado Dokuro-chan para o passado afim de impedi-lo de cometer esse ato hediondo, mas como de costume, o anjo acaba simpatizando com Sakura e ao invés de mata-lo irá impedi-lo de fazer essa coisa hedionda de outra maneira. Mas infelizmente ela acaba matando ele de uma maneira horrível e dolorosa toda vez que é contrariada com seu porrete “Excaliborg”, mas o ressuscita em seguida. Fica nesse ciclo de morre e ressuscita, morre e ressuscita, ressuscita e morre… pobre garoto, um sofrimento pior que a morte! XD
É humor negro e “joselito” dos bons. Recomendado! Cada episódio tem cerca de 10 minutos, ou seja serão 2 horas de muita risada, mesmo que você assista e não goste desse anime, pense: “foram apenas duas horas”.

HQL para SQL (Java)

Quem já usou Hibernate sabe de alguma de suas limitações no momento de fazer alguma query, muitas vezes não entendemos o motivo de não trazer o resultado correto, para entender seria bom ver o código na linguagem SQL que ele montou. Esse código em Java faz isso, traz pra você a tradução do seu código HQL.

// Pega-se o seu provedor do seu objeto  EntityManager como sessão
org.hibernate.Session session = (org.hibernate.Session) getEntityManager().getDelegate();

//Objetos de auxilio para simular a execução e traduzir a query HQL
final QueryTranslatorFactory translatorFactory = new ASTQueryTranslatorFactory();
final SessionFactoryImplementor factory = (SessionFactoryImplementor) session.getSessionFactory();

String query = "Seu HQL aqui";

//Monta um tradutor de query
final QueryTranslator translator = translatorFactory.createQueryTranslator(query, query, Collections.EMPTY_MAP, factory);

translator.compile(Collections.EMPTY_MAP, false);

//Você pode exibir o resultado onde quiser
System.out.print(translator.getSQLString());

Yu Yu Hakusho

Ainda me lembro da falida Manchete onde exibia vários animes e tokusatsus. Yu Yu  Hakusho passou nessa época, mas infelizmente ele passava no mesmo horário de outro programa que meus responsáveis queriam assistir. Depois de quase uma década e meia assisti todos os episódios e filmes que lançaram, quem sabe um dia eu não leio o manga?

A Série - 112 Episódios [download]

A história segue o modelo  “história sem fim”, aquele mesmo modelo que descrevi sobre Rurouni Kenshin. Várias sagas sem um objetivo grande a se conquistar, a não ser o protagonista Yusuke ficar com sua amada Keiko. A história possui comédia, aventura e muitas lutas de artes marciais com super poderes.
Yusuke,  é um garoto com temperamento briguento mas que não o impede de ser uma pessoa justa e bondosa, não possui qualquer outra habilidade a não ser lutar. Sua amada é uma garota inteligente e esforçada e costumar dar porrada somente com o principal.  Yusuke ao longo de sua jornada faz inúmeros companheiros, sendo os principais Koenma, Botan, Kuwabara, Hiei e Kurama.
No início da série mostra um pouco da personalidade de Yusuke e como ele se tornou o detetive do Reikai (lugar onde as pessoas são julgadas após a morte) , suas primeiras missões.  e conhece seus principais companheiros que permaneceram na série até o fim. O clima inicial da série é bem divertido, sem revelações importante e com bastante inimigos sem muita importância até encontrarem Toguro.
Quando encontram Toguro inicia-se  na minha opinião o melhor arco da série, a saga do Torneio das Trevas. Hoje em dia, um torneio de artes maciais que decide o futuro do planeta já é algo muito clichê, mas mesmo assim não tira o mérito de ser uma saga bastante interessante. Nesse momento que conhecemos melhor sobre o passado e os poderes verdadeiros dos personagens Hiei, Kurama, Toguro e a mestra Genkai e o estilo que foi ensinado ao Yusuke. Minha crítica em relação a essa série é o momento da batalha decisiva na qual dão poderes demais para o Yusuke, o protagonista já estava a um nível acima de seus companheiros, porém ele recebe uma bolinha azul de sua mestra e fica muito mais forte, não contente ele retira uma espécie de algemas espirituais que continham seu poder (algo que nunca foi mencionado) e ainda libera muito mais poder quando vê seu amigo Kuwabara ser supostamente morto. Todo esse aumento de nível numa única luta, a impressão foi de um personagem jogando D&D ter aumentando 10 níveis após uma aventura!  :O
Após a saga de Toguro, vem um inimigo novo chamado Sensui que quer fazer a humanidade pagar pelos seus pecados, Yusuke como detetive do Reikai deve impedi-lo. Os novos inimigos que surgem possuem poderes diferentes daqueles tradicionais de luta mas que podem produzir uma enorme vantagem em combate proporcionando lutas bem diferentes. Esse arco foi fraco comparado ao outro, talvez a revelação mais importante foi a descoberta do ancestral de Yusuke. A última batalha contra Sensui foi sensacional, apesar de ter aqueles momentos o principal estar perdendo e ter alguma coisa pra despertar o seu outro poder oculto.
Enfim, a última saga dos três reis do Makai, onde cada convoca um youkai especial pra ajuda-los no momento próximo de uma inevitável guerra. Os convocados foram Yusuke, Hiei e Kurama, infelizmente o Kuwabara não participará ativamente dessa saga, dando lugar aos personagens que sobreviveram a Saga do Torneio das Trevas. Foi algo não esperado e interessante deixar o Kuwabara de fora, mas ao mesmo tempo ficou um vazio. Sem delongas, é outra história que possui um torneio que vai decidir o futuro de tudo e todos.
No final Yusuke volta pra sua amada Keiko, cada dos seus companheiros segue sua vida como deseja. Série boa, com lutas interessantes e outras bem clichê no estilo “despertar o poder no momento mais crítico”, muitos momentos de comédia, nada de história complexa e profunda e um desfecho satisfatório.

The Movie (The Golden Seal) [download]

Não sei porque chamaram isso de Yu Yu Hakusho o filme pois tem a duração e o roteiro de um episódio comum. Surge um vilão que seqüestra o Koenma e Yusuke e seus companheiros devem salva-lo. O “filme” é basicamente isso, Koenma sendo seqüestrado, o caminho cheio de armadilhas e inimigos para os heróis atravessarem, a batalha final contra o “boss” e o final com os protagonistas felizes.

Meikai Shitou Hen Honoo no Kizuna [download]

Esse filme teve uma duração maior, porém é o típico filme que a história não tem relação nenhuma com a da série original. Segue o esquema de surgir um vilão e mais alguns companheiros, assim cada herói da história terá um adversário pra enfrentar. Os planos do vilão prosseguem com êxito mesmo com seus companheiros sendo derrotados, então acontece inevitável a luta final que o principal derrota vilão coma força emprestada dos seus amigos.

Conclusão

Ótimo desenho de lutas estilo “Dragon Ball Z”, com a vantagem de possuir pouca enrolação ou fillers, além de possuir muitas cenas engraçadas. Esse anime não possui uma história profunda e complexa e nem fará você refletir sobre nada, portanto se você gosta de lutas com poderes e comédia sem se importar muito com a história será um ótimo entretenimento para você!