Heapsort

Origem: Wikipédia, a enciclopédia livre.

Índice

1 Introdução e História
2 Definição
3 Características
4 Funcionamento
5 Implementações
6 Ligações externas

[editar] Introdução e História

O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por selecção. Foi desenvolvido em 1964 por Robert W. Floyd e J.W.J. Williams.

[editar] Definição

Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espectacularmente ruins no pior cenário, quer em tempo de execução, quer no uso da memória. O Heapsort trabalha no lugar e o tempo de execução em pior cenário para ordenar n elementos é de O (n log n). Para valores de n, razoavelmente grande, o termo log n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar.

[editar] Características

Comparações no pior caso: 2n log₂n + O(n)
Trocas no pior caso: n log₂n + O(n)
Melhor e pior caso: O(n log₂n)

[editar] Funcionamento

O heapsort utiliza uma estrutura de dados chamada heap para ordenar os elementos a medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada.

A heap pode ser representada como uma árvore ou como um vetor. Para uma ordenação crescente, deve ser construído um heap máximo (o maior elemento fica na raiz).

[editar] Implementações

[editar] Código em C

heapsort(tipo a[], int n)
{
   int i = n/2, pai, filho;
   tipo t;
 
   for (;;)
   {
      if (i > 0)
      {
          i--;
          t = a[i];
      }
      else
      {
          n--;
          if (n == 0)
             return;
          t = a[n];
          a[n] = a[0];
      }
     
      pai = i;
      filho = i*2 + 1;
 
      while (filho < n)
      {
          if ((filho + 1 < n)  &&  (a[filho + 1] > a[filho]))
              filho++;
          if (a[filho] > t)
          {
             a[pai] = a[filho];
             pai = filho;
             filho = pai*2 + 1;
          }
          else
             break;
      }
      a[pai] = t;
   }
}

[editar] Código em C++

template<class T>
void heap_sort( std::vector<T> &lista )
{  
    int tam = static_cast<int>( lista.size() ), i;

    for( i = tam/2 - 1; i >= 0; --i )
    {
       maxHeapify(lista, i , tam );
    }

    std::vector<T>::reverse_iterator elem;

    for( elem = lista.rbegin(); elem != lista.rend(); elem++ )
    {
       std::iter_swap( elem, lista.begin() );
       maxHeapify( lista, 0, --tam );
    }
}

template<class T>
void maxHeapify( std::vector<T> &lista, const int pos, const int n ) 
{ 
    int max = 2 * pos + 1;

    if( max < n )
    { 
       if( (max+1) < n && lista.at(max) < lista.at(max+1) )
       {
          ++max;
       }
       if( lista.at(max) > lista.at(pos) ) 
       { 
          std::swap( lista[max], lista[pos] );
          maxHeapify( lista, max, n );
       }
    }
}

[editar] Código em Java

       public static void heapSort(int v [])
       {  
         buildMaxHeap(v);
         int n = v.length;

         for (int i = v.length - 1; i > 0; i--) 
         { 
            swap(v, i , 0);
            maxHeapify(v, 0, --n);
         }
       }
       private static void buildMaxHeap(int v[])
       { 
          for (int i = v.length/2 - 1; i >= 0; i--)
             maxHeapify(v, i , v. length );
       }
       private static void maxHeapify(int v [], int pos, int n) 
       { 
          int max = 2 * pos + 1, right = max + 1;
          if (max < n)
          { 
             if ( right < n && v[max] < v[right])
                max = right;
             if (v[max] > v[pos]) 
             { 
                swap(v, max, pos);
                maxHeapify(v, max, n);
             }
          }
       }

       public static void swap ( int [ ] v, int j, int aposJ )
       {
          int aux = 0;
          aux = v [ j ];
          v [ j ] = v [ aposJ ];
          v [ aposJ ] = aux;
       }