Heap Sort - Dúvidas - RESOLVIDO

6 respostas
douglaskd

Tenho que apresentar o HeapSort na faculdade, mais não consegui entende-lo,

o código se encontra em C# mais, esta bem parecido com java, e minha dúvida esta relacionada a lógica

public static class heap{

        public static void heapSort(int[] vetor)
            {
                buildMaxHeap(vetor);

                int tamanho = vetor.Length;
     
                for (int i = vetor.Length - 1; i > 0; i--)
                {
                    swap(vetor, i, 0);
                    maxHeapify(vetor, 0, --tamanho);
                }
            }


        private static void buildMaxHeap(int[] vetor)
            {
                for (int i = vetor.Length / 2 - 1; i >= 0; i--)
                {
                    maxHeapify(vetor, i, vetor.Length);
                    Console.WriteLine("Tamanho: " + i);
                }     
            
            }

        private static void maxHeapify(int[] vetor, int pos, int tamanho)
            {
                int max = 2 * pos + 1, right = max + 1;
                if (max < tamanho)
                {
                    if (right < tamanho && vetor[max] < vetor[right])
                        max = right;
                    if (vetor[max] > vetor[pos])
                    {
                        swap(vetor, max, pos);
                        maxHeapify(vetor, max, tamanho);
                    }
                }
            }
        
        public static void swap(int[] vetor, int j, int aposJ)
            
            {
                int aux = vetor[j];
                vetor[j] = vetor[aposJ];
                vetor[aposJ] = aux;
            }

        static void Main(string[] args)
        {
            int i = 0;
            int[] vetor = new int[10]{1,2,10,20,4,5,8,6,3,90};

            heapSort(vetor);

            while(i<10){
                Console.WriteLine(vetor[i]);
                i++;
            }
            Console.Read();
        }
    }

dúvidas:

1 - maxHeapify, o que é aquela variavel MAX e RIGHT dentro do método, o que aquele if esta comparando ? bem perdido...

desde ja agradeço a ajuda

6 Respostas

douglaskd

eu ja li este texto ai, entendi o funcionamento dele

que gera uma arvore depois garante que os pais são maiores que os filhos e etc…

o problema é entender o algoritimo mesmo.

L

Uma árvore heap é representada como um array. Para você obter os filhos de um elemento, vc precisa multiplicar sua posição por 2.

int max = 2 * pos + 1, right = max + 1;

aqui ele obtém as posições dos filhos (max e right) de pos.

if (right < tamanho && vetor[max] < vetor[right])   
                        max = right;

aqui ele verifica qual dos dois filhos possuem o maior valor

if (vetor[max] > vetor[pos])  
                    {  
                        swap(vetor, max, pos);  
                        maxHeapify(vetor, max, tamanho);  
                    }

e aqui verifica qual se o filho com o mair valor tem um valor maior que o pai, se sim, ele troca o pai com o filho e chama novamente a função para verificar se tudo esta ok

douglaskd

aqui ele pega o ultimo filho que é pai ?

for (int i = vetor.Length / 2 - 1; i >= 0; i--)
L

sim, aqui int i = vetor.Length / 2 - 1 ele pega o ultimo nó que possui um filho

douglaskd

valeu lord, exclareceu tudo,

fiz mais alguns testes, uns print da vida e consegui entender esse algoritmo.

valeu!

WellingtonRamos

Veja se ajuda:
http://www.lcad.icmc.usp.br/~nonato/ED/Ordenacao/node49.htm
Aqui tem uma explicação do que seria o heapify: http://www.lcad.icmc.usp.br/~nonato/ED/Ordenacao/node50.htm

Criado 29 de agosto de 2011
Ultima resposta 29 de ago. de 2011
Respostas 6
Participantes 3