2010/6/24 Johann Dirichlet <peterdirich...@gmail.com>
> Só me dá um pouco de teoria, ou onde eu posso achar: o que seria um heap?
>
Uma heap é uma árvore na qual cada vértice possui um valor numérico (este
valor numérico pode ser também chamado de chave).
A única propriedade que uma heap precisa respeitar é a seguinte: a chave de
um vértice é maior ou igual a chave de seus filhos (note que maior igual
aqui serve pra qualquer ordem linear na verdade, ou seja, poderia ser menor
ou igual também).
Geralmente as heaps são árvores binárias completas e podem ser expressas
numa sequência numérica (que simplifica a vida pra quem faz programas de
computador com elas). Seja a sequência xi. Para um vértice xi, seus filhos
são x(2*i) e x(2*i+1), o pai de um vértice xi é x(i/2) (arredondado para
baixo).
Como um checkpoint, verifique a propriedade de heap para a seguinte
sequência: {10, 5, 9, 3, 4, 7, 5} (x1 = 10)
Eu tô falando da heap binária completa pq geralmente é isso que se entende
quando se fala de heap.
--
[]'s
Lucas
