Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
luispt

Ajuda heapsort

Recommended Posts

luispt

Boas pessoal,

Eu tenho que implementar um algoritmo conhecido como upheap e downheap,

o problema disso tudo e que nao consigo criar funçoes para mudar,substuir valores que tejam na stack

Se puderem ajudar agradecia sff

esqueci me de referir que tou a implementar em java

Share this post


Link to post
Share on other sites
Warrior

Estou numa aula, mais tarde tento-te dar uma explicação.

Concentra-te em construir uma heap em primeiro lugar, o heapsort é só utilizar uma heap para ordenar.

Share this post


Link to post
Share on other sites
luispt

ok muito obrigado, essa parte ja eu consegui fazer felizmente falta so conseguir fazer o que escrevi acima

Share this post


Link to post
Share on other sites
Warrior

Antes de mais nada, estás a implementar a heap como um array/vector ou mesmo com os nós e as ligações entre eles? (a primeira é mais fácil)

Share this post


Link to post
Share on other sites
Warrior

Ora bem.. primeiro de tudo, é importante o teu array ser indexado 1-based. Ou seja, o primeiro elemento está na posição 1. Isto facilita particularmente as contas.

Vou assumir que isto é uma min-heap, ou seja, pretendes ter o menor valor à cabeça. Para uma max-heap o procedimento é semelhante. Como tal, podes guardar na posição 0 um valor representativo de -infinito. Isto remove-te casos especiais, sempre chatos.

Upheap é feito quando tu pretendes colocar um novo valor na heap. O valor começa na última posição, seja ela i, e enquanto for maior do que o seu pai (que como deves saber é o valor na posição i/2) fazes o swap dos dois elementos. Se colocares o -inf na posição 0, podes considerar o upheap completo.

O downheap é feito quando pretendes remover um elemento. Para tal, colocas o último valor do array na primeira posição e agora vais fazer swap entre esse valor e o menor dos seus filhos (desde que o filho seja menor que o pai).

O caso especial acontece quando um elemento só tem um filho, ou nenhum. Para evitar isto, podes inicializar todas as posições livre a +inf, e ele irá terminar na posição correcta. Tens só que ter cuidado para declarar o array com o dobro dos elementos necessários, caso contrário como é óbvio não podes fazer esta simplificação..

Isto foi das respostas menos estruturados que já criei, limitei-me a atirar tópicos para o ar porque já estou cansado..

Se tiveres alguma dúvida mais específica amanhã tento ajudar.

Share this post


Link to post
Share on other sites
luispt

Muito obrigado desde ja pois ajudou muito, ja acabei o trabalho e agradeço imenso a explicaçao.

Compreendo o cansaço vida de universitario nao e facil nao =\

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.