Heap Sort - Dúvidas - RESOLVIDO

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

[code]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();
    }
}[/code]

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

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.

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

aqui ele pega o ultimo filho que é pai ?

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

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

valeu lord, exclareceu tudo,

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

valeu!

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