Discussão:Heapsort

O que se quiz dizer com "O Heapsort trabalha no lugar"?. Que ele é um algoritmo estável? --Eduardo M. Rezende 04:22, 23 Abril 2006 (UTC)

É uma espécie de expressão pra dizer que não aloca excedente de memória, ou seja, alocando O(1). Em inglês o equivalente é dizer que ele trabalha 'in-place'. Elloá

Algoritmo

Estava testando a implementação em C,

Acho que não precisa da variável t, e a última troca.

Minha implementação em C++

void heapSort (std::vector<int >& input)
{
    int n = input.size();

    // get middle element
    int i = n * 0.5;

    while(true) 
    {
        if(i > 0)
        {
            // build heap
            i--;
        }
        else
        {
            // sort and reconstruct heap
            n--;
            if(n == 0)
            {
                return;
            }
            std::swap(input[0], input[n]);
        }

        int parent = i;
        int child = parent * 2 +1;

        // while there are children greater than parent
        while(child < n)
        {
            // check which is the greatest child
            if(child +1 < n && input[child + 1] > input [child])
            {
                child++;
            }

            // check if child is greater than parent
            if(input[child] > input[parent])
            {
                std::swap(input[child], input[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
}