ALGORITMO HEAPSORT PARA O 4º PERÍODO DE SISTEMAS

Um heap é uma estrutura de dados organizada como árvore binária. Existem dois tipos de heaps: Os heaps de máximo (max heap), em que o valor de todos os nós são menores que os de seus respectivos pais; e os heaps de mínimo (min heap), em que o valor todos os nós são maiores que os de seus respectivos pais. Assim, em um heap de máximo, o maior valor do conjunto está na raíz da árvore, enquanto no heap de mínimo a raíz armazena o menor valor existente.


void heapsort( vetor, elementos ) {    
     int i = n / 2;
     int t, pai, filho, inf, j;
     inf=1;
     while(inf){        
          if( i > 0 ) {
              i--;
              t = vet[i];            
          }else{
              n--;
              if ( n == 0 ) { return; }
              t = vet[n];              
              vet[n] = *vet;              
          }        
          pai = i;
          filho = 2 * pai + 1;                  
          while(filho<n) {                
                 if(filho+1<n && vet[filho+1]>vet[filho]){                                
                     filho++;
                 }                
                 if( vet[filho] > t ) {
                     vet[pai] = vet[filho];
                     pai = filho;
                     filho = 2 * pai + 1;
                 }else{
                       break;
                 }
          }        
          vet[pai] = t;        
     }
}