Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

luispt

Ajuda heapsort

Mensagens Recomendadas

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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 =\

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.