Heapsort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Heapsort

algoritmo heapsort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso \Theta(n\log n)
complexidade caso médio \Theta(n\log n)
complexidade melhor caso \Theta(n\log n)[1]
complexidade de espaços pior caso \Theta(n) total, \Theta(1) auxiliar
Algoritmos

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

Definição[editar | editar código-fonte]

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 lg n). Lê-se logaritmo (ou log) de "n" na base 2. Para valores de n, razoavelmente grandes, o termo lg n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar.

Características[editar | editar código-fonte]

  • Comparações no pior caso: 2n log2n + O(n) é o mesmo que 2n lgn + O(n)
  • Trocas no pior caso: n log2n + O(n) é o mesmo que n lgn + O(n)
  • Melhor e pior caso: O(n log2n) é o mesmo que O(n lgn)

Estabilidade[editar | editar código-fonte]

O Heapsort não é um algoritmo de ordenação estável. Porém, é possível adaptar a estrutura a ser ordenada de forma a tornar a ordenação estável. Cada elemento da estrutura adaptada deve ficar no formato de um par (elemento original, índice original). Assim, caso dois elementos sejam iguais, o desempate ocorrerá pelo índice na estrutura original.

Funcionamento[editar | editar código-fonte]

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, lembrando-se sempre de manter a propriedade de max-heap.

A heap pode ser representada como uma árvore (uma árvore binária com propriedades especiais[2] ) ou como um vetor. Para uma ordenação crescente, deve ser construído uma heap mínima (o menor elemento fica na raiz). Para uma ordenação decrescente, deve ser construído uma heap máxima (o maior elemento fica na raiz).

Implementações[editar | editar código-fonte]

Assembly x86-gas-Linux[editar | editar código-fonte]

/* void heap_sort_as(int *x, int n);*/
.globl heap_sort_as
heap_sort_as:
 pushl %ebp
 movl %esp, %ebp
 /* 8(%ebp) -> arranjo*/
 /* 12(%ebp) -> num de elementos *4 */
 movl 12(%ebp), %eax
 movl $4, %ebx
 mul %ebx
 pushl %eax
 pushl 8(%ebp)
 call montar_heap_as
 addl $4, %esp
 popl %eax
 subl $4, %eax          /* eax eh (n*4)-4*/
 /* faz a troca */
 movl 8(%ebp), %ebx     /* tmp = *x */
 pushl %eax
 movl %ebx, %ecx
 addl %eax, %ecx
 movl (%ebx), %eax
 movl (%ecx), %edx
 movl %eax, (%ecx)
 movl %edx, (%ebx)
 popl %eax              /* eax representa (n*4)-4 */
 pushl $0
 pushl %eax
 pushl 8(%ebp)
heap_sort_as_loop:
 cmp $1, %eax
 jle heap_sort_as_fim
 call man_heap_as
 movl 4(%esp), %eax
 subl $4, %eax
 /* faz a troca */
 movl 8(%ebp), %ebx     /* tmp = *x */
 pushl %eax
 movl %ebx, %ecx
 addl %eax, %ecx
 movl (%ebx), %eax
 movl (%ecx), %edx
 movl %eax, (%ecx)
 movl %edx, (%ebx)
 popl %eax              /* eax representa (n*4)-4 */
 movl %eax, 4(%esp
heap_sort_as_fim:
 leave
 ret
montar_heap_as:
 pushl %ebp
 movl %esp, %ebp
 /* 8(%ebp) -> arranjo*/
 /* 12(%ebp) -> num de elementos *4 */
 movl 12(%ebp), %eax
 movl $2, %ecx
 cltd
 idivl %ecx
 movl $4, %ecx
 cltd
 idivl %ecx
 mul %ecx
 subl $4, %eax /* eax eh h*/
 pushl %eax
 pushl 12(%ebp)
 pushl 8(%ebp)
montar_heap_as_whmz:
 cmp $0, %eax
 jl montar_heap_as_fim
 call man_heap_as
 movl 8(%esp), %eax
 subl $4, %eax
 movl %eax, 8(%esp)
 jmp montar_heap_as_whmz
montar_heap_as_fim:
 leave
 ret
man_heap_as:
 pushl %ebp
 movl %esp, %ebp
 /* 8(%ebp) -> arranjo */
 /* 12(%ebp) -> num de elementos *4 */
 /* 16(%ebp) -> pai *4 */
 movl 16(%ebp), %eax
 pushl %eax
 movl $2, %ebx
 mul %ebx
 addl $4, %eax             /* agora eax eh f*/
man_heap_as_wfmn:
 cmp 12(%ebp), %eax
 jge man_heap_as_fim
 movl %eax, %ebx
 addl $4, %ebx             /* ebx eh f2 */
 movl 8(%ebp),%edx
 addl %eax, %edx           /* edx aponta p/ x[f] */
 movl (%edx), %edx
 cmp 12(%ebp), %ebx
 jge man_heap_as_testetroca
 movl 8(%ebp), %ecx
 addl %ebx, %ecx          /* ecx aponta p/ x[f2] */
 movl (%ecx), %ecx
 cmp %edx, %ecx
 jle man_heap_as_testetroca
 movl %ebx, %eax          /* f=f2 ou seja maior filho eh f2 */
 movl %ecx, %edx          /* movimentacao apenas p/ testar */
man_heap_as_testetroca:
 popl %ebx           /* ebx eh p */
 movl 8(%ebp), %ecx
 addl %ebx, %ecx     /* ecx eh x[p]*/
 movl (%ecx), %ecx
 cmp %ecx, %edx
 jle man_heap_as_fim
 /*fazer a troca */
 pushl %eax          /* salva f na pilha*/
 addl 8(%ebp), %eax
 movl %ecx, (%eax)   /* x[f] = x[p] */
 addl 8(%ebp), %ebx
 movl %edx, (%ebx)   /* x[p] = x[f] */
 movl (%esp), %eax
 movl $2, %ebx
 mul %ebx
 addl $4, %eax
 jmp man_heap_as_wfmn
man_heap_as_fim:
 leave
 ret

Código em C[editar | editar código-fonte]

void heapsort(tipo a[], int n)
{
   int i = n/2, pai, filho, t;
 
   for (;;)
   {
      if (i > 0)
      {
          i--;
          t = a[i];
      }
      else
      {
          n--;
          if (n == 0)
             return;
          t = a[n];
          a[n] = a[0];
      }
 
      pai = i;
 
      //Primeiro será feita a comparação com o filho da esquerda.
      filho = i*2;
 
      while (filho < n)
      {
         //Se o filho da esquerda for menor do que o filho da direita,então será feita a troca do filho que será comparado.
          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;
   }
}

Código em C++[editar | editar código-fonte]

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 );
       }
    }
}

Código em C#[editar | editar código-fonte]

        public 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 = v[j];
            v[j] = v[aposJ];
            v[aposJ] = aux;
        }

Código em Java[editar | editar código-fonte]

       public static void heapSort(int[] v)
       {
         buildMaxHeap(v+1);
         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 maxi;
          int l = 2 * pos + 1;
          int right = 2 * pos + 2;
          if ( (l < n) && (v[l] > v[pos]) )
          {
             maxi = l;
          }
          else
          {
             maxi = pos;
          }
          if (right < n && v[right] > v[maxi])
          {
             maxi = right;
          }
          if (maxi != pos)
          {
             swap(v, pos, maxi);
             maxHeapify(v, maxi, n);
          }
       }
 
       public static void swap ( int[ ] v, int j, int aposJ )
       {
          int aux = v [ j ];
          v [ j ] = v [ aposJ ];
          v [ aposJ ] = aux;
       }

Código em Java (5.0)[editar | editar código-fonte]

    public static <T extends Comparable<? super T>> void heapSort(T[] 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 <T extends Comparable<? super T>> void buildMaxHeap(T v[]) {
        for (int i = v.length / 2 - 1; i >= 0; i--)
            maxHeapify(v, i, v.length);
    }
 
    private static <T extends Comparable<? super T>> void maxHeapify(T[] v, int pos,
            int n) {
        int max = 2 * pos + 1, right = max + 1;
        if (max < n) {
            if (right < n && v[max].compareTo(v[right]) < 0)
                max = right;
            if (v[max].compareTo(v[pos]) > 0) {
                swap(v, max, pos);
                maxHeapify(v, max, n);
            }
        }
    }
 
    public static void swap(Object[] v, int j, int aposJ) {
        Object aux = v[j];
        v[j] = v[aposJ];
        v[aposJ] = aux;
    }

Código em python[editar | editar código-fonte]

def heapsort(lst):
  ''' Heapsort. Note: this function sorts in-place (it mutates the list). '''
 
# in pseudo-code, heapify only called once, so inline it here
  for start in range((len(lst)-2)/2, -1, -1):
    siftdown(lst, start, len(lst)-1)
 
  for end in range(len(lst)-1, 0, -1):
    lst[end], lst[0] = lst[0], lst[end]
    siftdown(lst, 0, end - 1)
  return lst
 
def siftdown(lst, start, end):
  root = start
  while True:
    child = root * 2 + 1
    if child > end: break
    if child + 1 <= end and lst[child] < lst[child + 1]:
      child += 1
    if lst[root] < lst[child]:
      lst[root], lst[child] = lst[child], lst[root]
      root = child
    else:
      break

Código em PHP[editar | editar código-fonte]

<?php
function buildheap(&$vet, $i, $f)
{
 $aux = $vet[$i];
 $j = $i * 2 + 1;
 
 while ($j <= $f)
 {
 if($j < $f)
 {
 if($vet[$j] < $vet[$j + 1]) {
 $j = $j + 1;
 }
 }
 if($aux < $vet[$j])
 {
 $vet[$i] = $vet[$j];
 $i = $j;
 $j = 2 * $i + 1;
 }
 else
 {
 $j = $f + 1;
 }
 }
 $vet[$i] = $aux;
}
 
function heapsort(&$vet)
{
 for($i=(int)((count($vet) - 1) / 2); $i >= 0; $i--)
 {
 $count = count($vet) - 1;
 buildheap($vet, $i, $count);
 }
 
 for ($i = (count($vet) - 1); $i >= 1; $i--)
 {
 $aux = $vet[0];
 $vet [0] = $vet [$i];
 $vet [$i] = $aux;
 buildheap($vet, 0, $i - 1);
 }
}
?>

Referências

  1. [1]
  2. BAASE, Sara. Computer Algorithms: Introduction to Design and Analysis (em inglês). 2ª ed. Reading, Massachusetts: Addison-Wesley, 1988. 71 p. ISBN 0-201-06035-3

Ligações externas[editar | editar código-fonte]

Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.